题解 P4401 【[IOI2007]Miners 矿工配餐】

SIGSEGV

2018-07-30 09:39:07

Solution

经典的滚动数组啊....... 方程没什么难的,各位dalao都已经讲过了:f[i][a][b][c][d]:第一矿场前两次吃a,b 第二矿场前两次吃c,d的最大价值。 直接上代码吧(滚动技巧见代码): ```cpp #include <bits/stdc++.h> using namespace std; int dp[2][4][4][4][4],n; char s[100004]; int sub(char s) //返回对应的下标 { if (s == 'M') return 2; if (s == 'F') return 3; return 1; } int val(int a,int b,int c) //第一次吃a,第二次吃b,第3次吃c,产出的价值 { int ret = 1; if (a && a != b && a != c) ret++; if (b && b != c) ret++; return ret; } int main () { scanf("%d",&n);scanf("%s",s + 1);//读入操作 memset(dp,-1,sizeof(dp)); dp[0][0][0][0][0] = 0; for (int i = 1;i <= n;i++) { for (int a1 = 0;a1 < 4;a1++) for (int a2 = 0;a2 < 4;a2++) for (int a3 = 0;a3 < 4;a3++) for (int a4 = 0;a4 < 4;a4++) { if (dp[(i + 1) % 2][a1][a2][a3][a4] == -1) continue;//上一轮的当前状态不存在,无法推出下一个 int b = sub(s[i]); dp[i % 2][a2][b][a3][a4] = max(dp[i % 2][a2][b][a3][a4], dp[(i + 1) % 2][a1][a2][a3][a4] + val(a1,a2,b));//送给第一个煤矿(i % 2是滚动操作) dp[i % 2][a1][a2][a4][b] = max(dp[i % 2][a1][a2][a4][b], dp[(i + 1) % 2][a1][a2][a3][a4] + val(a3,a4,b));//送给第二个煤矿 } memset(dp[(i + 1) % 2],-1,sizeof(dp[(i + 1) % 2]));//清空上一轮的递推状态 } int ans = 0; for (int a1 = 0;a1 < 4;a1++) for (int a2 = 0;a2 < 4;a2++) for (int a3 = 0;a3 < 4;a3++) for (int a4 = 0;a4 < 4;a4++) ans = max(ans,dp[n % 2][a1][a2][a3][a4]); printf("%d",ans); return 3; } ```