Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-29

SRM453.5 div1 (過去問)

16:28

Medium - PlanarGraphShop

top submissionをみて修正. まずグラフのエッジ数はwikipediaのplanar graph(平面グラフ)の項によると (ノード数*3-6) となります.

Planar graph - Wikipedia

平面グラフ - Wikipedia

またコストの計算と同時に最小値の計算も行って, 計算時間を短縮しています.

class PlanarGraphShop {
public:
  int bestCount(int N) {
    int ret = 0;
    vector <int> dp(N+1, INT_MAX);
    dp[0] = 0;
    
    for (int nodes=1; nodes<=36; nodes++) {
      int limit = 3 * nodes - 6;
      if (nodes == 1) limit = 0;
      if (nodes == 2) limit = 1;
      for (int edges=0; edges<=limit; edges++) {
        int cost = (int)pow((double)nodes, 3) + (int)pow((double)edges, 2);
        for (int i=0; i<=N-cost; i++)
          dp[i+cost] = min(dp[i] + 1, dp[i+cost]);
      }
    }

    ret = dp[N];
    return ret;
  }
};