【动态规划/递推】BZOJ1806[IOI2007]- Miners

IOI历史上的著名水题，我这种蒟蒻都能写的东西。

【思路】

用1、2、3分别代替三种食物，0表示当前矿井没有食物。f[i][a][b][c][d]当前第i个食物，矿1的食物顺序由上至下为a,b；矿2的食物顺序由上至下为c,d。

判断产物数量的方法很巧妙，由下至上a,b,c。初始时默认投入一个食物至少生产一单位，如果a为有食物且与bc不同，则加一单位；如果b为有食物且与c不同，再加一个单位。最后加一个滚动数组就可以了。

【错因】

1.因为a,b,c,d大小范围是0..3，但是我把下标范围写3！一定要写4！我就是一不小心写错了，居然改了两个晚上，完全没有考虑到错因在这里....

2.还有初始化的时候只有f[0][0][0][0][0]是0，不要把所有第一位是0的都写成0了..

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int MAXN=+;

 int n;

 int food[MAXN];

 int f[][][][][];//f[i][a][b][c][d]当前第i个食物，矿1的食物顺序由上至下为a,b；矿2的食物顺序由上至下为c,d。

 int compare(int x,int y,int z)

 {

     int t=;

     if (x!= && x!=y && x!=z) t++;

     if (y!= && y!=z) t++;

     return t;

 }

 int main()

 {

     scanf("%d",&n);

     getchar();

     for (int i=;i<n;i++)

     {

         char c;

         scanf("%c",&c);

         if (c=='M') food[i]=;

         if (c=='F') food[i]=;

         if (c=='B') food[i]=;

     }

     memset(f,-,sizeof(f));

     f[][][][][]=;     int ans=-;

     for (int i=;i<n;i++)

         for (int a=;a<=;a++)

             for (int b=;b<=;b++)

                 for (int c=;c<=;c++)

                     for (int d=;d<=;d++)

                     {

                         if (f[i%][a][b][c][d]==-) continue;

                         int add1=compare(b,a,food[i]),add2=compare(d,c,food[i]);

                         int x=food[i];

                         f[(i+)%][x][a][c][d]=max(f[(i+)%][x][a][c][d],f[i%][a][b][c][d]+add1);

                         f[(i+)%][a][b][x][c]=max(f[(i+)%][a][b][x][c],f[i%][a][b][c][d]+add2);

                         if ((i==n-) && (f[(i+)%][x][a][c][d]>ans)) ans=f[(i+)%][x][a][c][d];

                         if ((i==n-) && (f[(i+)%][a][b][x][c]>ans)) ans=f[(i+)%][a][b][x][c];

                     }

     cout<<ans<<endl;

     return ;

 }