警示后人
查看原帖
警示后人
1032391
ICE__LX楼主2025/7/31 09:26

这是错误的转移:

for(int i = 1 ; i <= m ; i ++) {
		for(int a = 0 ; a <= t[1] ; a ++) {
			for(int b = 0 ; b <= t[2] ; b ++) {
				for(int c = 0 ; c <= t[3] ; c ++) {
					if(a + b + c <= i) {
						int d = i - a - b - c;
						if(d > t[4]) continue;
						int j = 1 + a + 2 * b + 3 * c + 4 * d;
						if(d) dp[a][b][c] += w[j];
						if(a) dp[a][b][c] = max(dp[a][b][c] , dp[a - 1][b][c] + w[j]);
						if(b) dp[a][b][c] = max(dp[a][b][c] , dp[a][b - 1][c] + w[j]);
						if(c) dp[a][b][c] = max(dp[a][b][c] , dp[a][b][c - 1] + w[j]);
					}
				}
			}
		}
	}

这是正确的转移:

for(int i = 1 ; i <= m ; i ++) {
		for(int a = t[1] ; a >= 0 ; a --) {
			for(int b = t[2] ; b >= 0 ; b --) {
				for(int c = t[3] ; c >= 0 ; c --) {
					if(a + b + c <= i) {
						int d = i - a - b - c;
						if(d > t[4]) continue;
						int j = 1 + a + 2 * b + 3 * c + 4 * d;
						if(d) dp[a][b][c] += w[j];
						if(a) dp[a][b][c] = max(dp[a][b][c] , dp[a - 1][b][c] + w[j]);
						if(b) dp[a][b][c] = max(dp[a][b][c] , dp[a][b - 1][c] + w[j]);
						if(c) dp[a][b][c] = max(dp[a][b][c] , dp[a][b][c - 1] + w[j]);
					}
				}
			}
		}
	}

一定要从后往前枚举!这样才满足无后效应!

2025/7/31 09:26
加载中...