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

· · 题解

AC的第一道IOI题目，发个题解纪念一下。

这个题是一个相当基础的dp，唯一的难点在于代码实现。

令dp[i][a1][a2][b1][b2]为当前送第i辆车，第一个矿前两次送a1和a2，第二个前两次送b1和b2。

然后直接看这辆车送第一个矿还是第二个就好了。

边界是第n+1辆车，某个矿前两辆车没送的情况就直接用0占位就好。

这里用的是记忆化，由于数据小，时空问题都不大。如果觉得记忆化可能会MLE/爆栈可以改用逆序dp（可以把i滚动掉），但是代码会复杂很多，不如记忆化好写，像我这样的萌新可以先用记忆化写一遍，再照着写dp。

代码：

#include <iostream>
#include <cstdio>
using namespace std;
int n,type[100010],dp[100010][4][4][4][4];
char ch;
char getchar(int){
    char c='\0';
    while(c!='M' && c!='F' && c!='B')c=getchar();
    return c;
}
int food(char c){
    if(c=='M')return 1;
    if(c=='F')return 2;
    if(c=='B')return 3;
    return -1;
}
int coal(int fa,int fb,int fc){
    if(!fa && !fb)return 1;
    if(!fa)return (fb!=fc)+1;
    if(fa==fb && fb==fc)return 1;
    return (fa!=fb)+(fb!=fc)+(fa!=fc);
}
int dfs(int now,int a1,int a2,int b1,int b2){
    if(now>n)return 0;
    if(dp[now][a1][a2][b1][b2])return dp[now][a1][a2][b1][b2];
    return dp[now][a1][a2][b1][b2]=max(dfs(now+1,a2,type[now],b1,b2)+coal(a1,a2,type[now]),dfs(now+1,a1,a2,b2,type[now])+coal(b1,b2,type[now]));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        ch=getchar(233);
        type[i]=food(ch);
    }
    printf("%d\n",dfs(1,0,0,0,0));
    return 0;
}