[2019.1.1]BZOJ1806 [Ioi2007]Miners 矿工配餐

一看到IOI2007,又是紫题,一脸惊恐...

然后就被我秒了233

我们令一个数字表示一种食物。

设(dp_{i,a,b,c,d})表示运完第(i)辆食物,煤矿1的上次食物是(b),上上次是(a),煤矿2的上次食物是(d),上上次是(c)。

设第(x)次的食物是(f_x),令(i,j,k)中不同食物的数量是(PC(i,j,k)),我们枚举(a,b,c,d),得到转移

(dp_{x,b,f_x,c,d}=max{dp_{x-1,a,b,c,d}+PC(a,b,f_x)})

(dp_{x,a,b,d,f_x}=max{dp_{x-1,a,b,c,d}+PC(a,b,f_x)})

到这里,你已经会了。于是你去写代码。

高高兴兴地提交,然后你发现你MLE了。

因为我还没讲完。。。

因为这题内存很小(各大OJ不一,BZOJ是(64MB),已经很仁慈了,IOI原题是(16MB)),所以我们要滚存。

然后没了,真的没了,你真的可以写代码去了。

然后你可能WA了。

因为要注意边界情况。

code:

#include<bits/stdc++.h>
using namespace std;
int n,s,k,dp[2][4][4][4][4],mx;
void scan(int &x){
    x=0;
    while(x!='B'&&x!='F'&&x!='M')x=getchar();
    x=(x=='B'?1:(x=='F'?2:3));
}
int PC(int x,int y,int z){
    int tot=0;
    if(x)tot++;
    if(y&&y!=x)tot++;
    if(z&&z!=y&&z!=x)tot++;
    return tot;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++,k^=1){
        scan(s);
        if(i==1){
            dp[k^1][0][s][0][0]=dp[k^1][0][0][0][s]=1;
            continue;
        }
        for(int a=0;a<=3;a++)for(int b=0;b<=3;b++)for(int c=0;c<=3;c++)for(int d=0;d<=3;d++){
            if(dp[k][a][b][c][d]){
                dp[k^1][b][s][c][d]=max(dp[k][a][b][c][d]+PC(a,b,s),dp[k^1][b][s][c][d]);
                dp[k^1][a][b][d][s]=max(dp[k][a][b][c][d]+PC(c,d,s),dp[k^1][a][b][d][s]);
            }
        }
        memset(dp[k],0,sizeof(dp[k]));
    }
    for(int a=0;a<=3;a++)for(int b=0;b<=3;b++)for(int c=0;c<=3;c++)for(int d=0;d<=3;d++)mx=max(mx,dp[k][a][b][c][d]);
    printf("%d",mx);
    return 0;
}