最初問題文を読み間違えたけど、後は簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=11536
問題
N箇所の芝があり、それぞれ初期状態の高さはinit[i]で、以後1日ごとにgrow[i]芝が高くなる。
毎日、grow[i]芝が伸びた後、1か所芝を刈って高さを0にすることができる。
刈った場所は、また翌日からgrow[i]ずつ高くなっていく。
N箇所合計の芝の高さをH以下にできるか、できるなら最短日数を答えよ。
解法
まず、芝はどれだけ伸びても1回で高さ0に出来るので、同じ場所を2回刈る必要はない。
また、刈った後も芝が伸びていくので、高さの総和を抑えるにはgrow[i]が低い順に刈るのが良い。
よって、まずgrow[i]昇順に芝をソートする。
次に、H以下になる目標日数dを0~N日で総当たりする。
各目標日数dについては、DPを用いてN箇所のうちその日数分のみ選択して芝を刈り、合計を最小化していく。
i日目に芝を刈った場所は、d日目には(d-i)*growだけ高くなる。
合計が初めてH以下になった日が答え。
N日芝を刈ってもダメだら、何日経っても達成不可。
O(N^3)で解答可能。
int dpdp[52][52]; class CuttingGrass { public: int theMin(vector <int> init, vector <int> grow, int H) { int N=init.size(); pair<int,int> P[51]; int i,d,x,y; FOR(i,N) P[i]=make_pair(grow[i],init[i]); sort(P,P+N); FOR(d,N+1) { ZERO(dpdp); FILL_INT(dpdp,1<<29); dpdp[0][0]=0; FOR(x,N) { FOR(y,d+1) { dpdp[x+1][y+1] = min(dpdp[x+1][y+1],dpdp[x][y]+(d-(y+1))*P[x].first); dpdp[x+1][y] = min(dpdp[x+1][y],dpdp[x][y]+P[x].second+d*P[x].first); } } if(dpdp[N][d]<=H) return d; } return -1; } };
まとめ
先に答えを仮置きし、それを達成可能かチェックする問題はたまにでるね。
DPか二分探索系。