这是错误的转移:
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]);
}
}
}
}
}
一定要从后往前枚举!这样才满足无后效应!