#include <stdio.h>
#include <string.h>

#define MAXN 30
#define MAXM 300
#define INF 0x3333333

int dp[MAXN][MAXM], path[MAXN][MAXM], f[MAXN], t[MAXN], d[MAXN], times[MAXN], m;

int sum(int i, int time){
	int ans  = (f[i] + f[i] - d[i] * (time - 1)) * time / 2;
	return ans;
}

void Gettimes(int p, int time){
	if(p <= 1) return;
	m -= (times[p] = time) + t[p];
	Gettimes(p - 1, path[p - 1][m]);
}

int main(){
	int n, i, j, k, temp, CASE = 0;
	//freopen("output.out", "w", stdout);
	while(~scanf("%d", &n), n){
		scanf("%d", &m);
		m = m * 12;
		for(i = 0; i <= n; i ++)
			for(j = 0; j <= m; j ++)
				if(!i) dp[i][j] = 0;
				else dp[i][j] = -1;
		memset(path, -1, sizeof(path));
		t[1] = 0;
		for(i = 1; i <= n; i ++) scanf("%d", &f[i]);
		for(i = 1; i <= n; i ++) scanf("%d", &d[i]);
		for(i = 2; i <= n; i ++) scanf("%d", &t[i]);
		int max = - INF, p;
		for(i = 1; i <= n; i ++){
			for(j = t[i]; j <= m; j ++){
				for(k = 0; k <= j - t[i]; k ++)
					if(dp[i - 1][k] > -1 && dp[i - 1][k] + sum(i, j - k - t[i]) >= dp[i][j]){
						dp[i][j] = dp[i - 1][k] + sum(i, j - k - t[i]);
						path[i][j] = j - k - t[i];
					}
				if(j > 0 && path[i][j - 1] != -1){
					temp = (f[i] - path[i][j - 1] * d[i]) < 0 ? 0 : (f[i] - path[i][j - 1] * d[i]);
					if(dp[i][j] < dp[i][j - 1] + temp){
						dp[i][j] = dp[i][j - 1] + temp;
						path[i][j] = path[i][j - 1] + 1;
					}
				}
			}
			if(max < dp[i][m]){max = dp[i][m]; p = i;}
		}
		memset(times, 0, sizeof(times));
		Gettimes(p, path[p][m]);
		times[1] = m;
		if(CASE) printf("\n");
		for(i = 1; i < n; i ++) printf("%d, ", times[i] * 5);
		printf("%d\n", times[n] * 5);
		printf("Number of fish expected: %d\n", max);
		CASE = 1;
	}
	return 0;
}

• Re:dp方法很好，这题挺适合dp的 (1896) zyz913614263 2011-12-19 16:28:07
• Re:dp方法过了！！！！！！！ (1896) zsbpro 2012-03-13 20:51:46