题解 P4401 【[IOI2007]Miners 矿工配餐】
SIGSEGV
2018-07-30 09:39:07
经典的滚动数组啊.......
方程没什么难的,各位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;
}
```