PKU 1042 Gone Fishing

問題

n個の湖でhの制限時間内で釣りをする。

最初、1番の湖から出発する。
i番目の湖からはi+1番目の湖に行くか、その湖で釣りを終了するかしかできない。
i番目の湖からi+1番目の湖へはt[i]の時間がかかる。

i番目の湖では最初の1単位時間ではf[i]の魚が取れるが、
次の単位時間からはd[i]ずつ取れる魚が減っていく。（マイナスになることはない）

最も魚の取れる取り方を出力せよ。
そのような取り方が複数ある場合、1番目の湖で釣りをする時間を最大に、
それでも複数ある場合2番目の湖で釣りをする時間を最大に……というようにするものとする。

制約条件

n≦25
h≦200くらい

方針

dp[i][j]を湖iまでで、j時間の時間が残っているときの釣れる魚の最大数として、メモ化再帰 + 経路復元。

途中の湖で釣りを切り上げる場合があるのでそれもちゃんと実装する。

ソースコード

int n, h, f[30], d[30], T[30];
int dp[30][300], ans[30], next[30][300];

int rec(int c, int t){
	int &res = dp[c][t];
	if(res >= 0) return res;
	res = 0;
	int fish = 0, mxi = -1;
	bool finish = 0;
	
	for(int i = 0; i <= t; i++){
		if(c < n - 1 && t - i >= T[c]){
			int tmp = rec(c + 1, t - i - T[c]) + fish;
			if(res <= tmp) res = tmp, mxi = i, finish = 0;
		}
		int tmp = fish;
		if(res <= tmp) res = tmp, mxi = i, finish = 1;
		
		fish += max(0, f[c] - i * d[c]);
	}
	next[c][t] = finish ? -1 : mxi;
	return res;
}

int main(){
	int cs = 0;
	while(cin >> n, n){
		if(cs++) cout << endl;
		
		cin >> h;
		rep(i, n) cin >> f[i];
		rep(i, n) cin >> d[i];
		rep(i, n - 1) cin >> T[i];
		
		memset(ans, 0, sizeof(ans));
		memset(dp, -1, sizeof(dp));
		
		rec(0, h * 12);
		int t = h * 12;
		rep(i, n){
			if(next[i][t] < 0){
				ans[i] = t * 5; break;
			}
			ans[i] = next[i][t] * 5;
			t -= next[i][t] + T[i];
		}
		rep(i, n) cout << ans[i] << (i == n - 1 ? "\n" : ", ");
		printf("Number of fish expected: %d\n", dp[0][h * 12]);
	}
	return 0;
}