TopCoder SRM 642 Div1 Medium TaroCutting

似たような問題考えてたけど、自力で解けなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=13319

問題

N本の木がある。
各木の高さの初期値はH[i]で、１日あたりA[i]高さが伸びる。

ここで、M個の機械がある。
各機械には設定値D[i]があり、この機械を使うとD[i]以上の木の高さをD[i]に切ることができる。

ただし、各機械は１日あたり１本の木にしか使うことができない。

T日後の木の高さの総和を最小化せよ。

解法

N,M,T≦150なので、O(N*M*T)なんだろうなと思ったけど自力回答できず。
結局周りの回答を見て解いた。
O(N*M*T)なDPを用いる方法と、最小コストフローを用いる方法があったようだ。
以下はDP解を紹介。

D[i]の機械をTからtだけ前の時点でj番の木に適用すると、その木は時刻Tには高さがD[i]+t*A[j]となることが期待できる。
このアイデアを元に、時刻Tから1ずつ巻き戻すDPを考える。

当然、A[j]の大きな木はtが小さい段階(Tに近い時刻)で優先的に切るようにしておきたい。
また、その際はD[i]の小さな機械を優先的に適用したい。
そこで、事前に木をA[i]の大きい順、機械をD[i]の小さい順にソートしておく。

各時刻のループでは、各木にデバイスを使う/使わない場合の木の高さの総和を更新していけば良い。
DPの順番に注意。

int dp[152][152][152];

class TaroCutting {
	public:
	pair<int,int> T[151];
	int getNumber(vector <int> height, vector <int> add, vector <int> device, int time) {
		int N=height.size();
		int D=device.size();
		int i,j,x,y;
		FOR(i,N) T[i]=make_pair(add[i],height[i]);
		sort(T,T+N);
		reverse(T,T+N);
		sort(device.begin(),device.end());
		
		FOR(i,N+1) FOR(x,D+1) FOR(y,time+1) dp[i][x][y]=1<<29;
		dp[0][0][0]=0;
		FOR(y,time+1) FOR(i,N+1) FOR(x,D+1) {
			int cur=dp[i][x][y];
			
			dp[i][x+1][y]=min(dp[i][x+1][y],cur);
			dp[i][0][y+1]=min(dp[i][0][y+1],cur);
			
			if(i<N) dp[i+1][x][y]=min(dp[i+1][x][y], cur+T[i].second+T[i].first*time);
			if(y<time&&i<N&&x<D) dp[i+1][x+1][y]=min(dp[i+1][x+1][y],cur+device[x]+y*T[i].first);
		}
		
		int mi=1<<29;
		FOR(x,D+1) FOR(y,time+1) mi=min(mi,dp[N][x][y]);
		return mi;
	}
}

まとめ

数値の制限から、想定解はDPかな。
最小コストフローは思いつかないわ…。