SRM 517 Div2 Hard CuttingGrass

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11536&rd=14542
複数の木があり、それらの高さはinit[i]である。毎ターンそれぞれの木はgrow[i]だけ成長する。そしてあなたは毎ターンどれかの木を切る。切るとその木は高さが0になる。
木の高さの和をH以下に抑えられるように木を切っていく時、最短何ターンでこれを達成できるか？達成不可なら-1を返せ。

やりかた

Editorialを参考にしました。

まずある木を切ると高さが0になってしまうことから同じ木を複数回切る必要はないことはわかる。するとせいぜい木の本数だけターンを行い、それでも目標が達成できなければ、達成不可ということになる。

ここで毎ターンごとに木を切るわけだが、そのターンが終了した時点での切った長さの総長を最大化（これをLとする）し、

木を全く切らなかった際の木の全長 - L <= H （★）

が成立すればそのターンで達成できるという事になる。
そしてあるターンで切る木はその前のターンで切る木より、成長速度grow[i]の値が速い方がいい。速く育つ木は後々切ったほうが効果的だからだ。てことはgrowをまずソートした上で、j番目までの木を見て、i本の木を切った時の切った長さの総長をdp[i][j]をしたとき、以下の動的計画法でこれをもとめることができる。

dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j] + init[j] + (i + 1) * grow[j])

左辺第一項はj番目の木を切らなかった時、第二項はj番目を切った時の切った総長になる。

あとは★が成り立つ最小のターン数をそこから調べればいい。なければ-1。

以下ソース。

int dp[51][51];

class CuttingGrass {
public:
  //要素数が同じvectorをaをキーにしてソート
  void tupplesort(vector<int> &a, vector<int> &b){
    vector<pair<int, int> > p;
    for(int i = 0; i < (int)a.size(); i++)
      p.push_back(make_pair(a[i], b[i]));
    sort(p.begin(), p.end());
    for(int i = 0; i < (int)a.size(); i++){
      a[i] = p[i].first;
      b[i] = p[i].second;
    }
    return;
  }

  int theMin(vector <int> init, vector <int> grow, int H) {
    if(accumulate(ALL(init), 0) <= H) return 0;
    int N = init.size(); 
    tupplesort(grow, init);
    memset(dp, 0, sizeof(dp));
    for(int t = 0; t < N; t++)
      for(int i = 0; i < N; i++)
	dp[t + 1][i + 1] = max(dp[t + 1][i], dp[t][i] + init[i] + (t + 1) * grow[i]);

    for(int t = 0; t <= N; t++){
      if(accumulate(ALL(init), 0) + accumulate(ALL(grow), 0) * t - H 
	 <= dp[t][N]) return t;
    }
    return -1;
  }
};

またdpということでとけなかった。悔い改めて。

initというオフセットがなければ、貪欲でも解けるのだろう。ずっとこの方法を試していた。
あとgrassなので木じゃなくて草ですね。