BZOJ-1806: [Ioi2007]Miners 矿工配餐

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1806

思路：这是一道很裸的动态规划。确定状态f[i][a][b][c][d]表示送了第i次餐车后，第一个矿场的最后两次送餐是a，b第二个矿场的最后两次送餐是c，d，然后直接递推就可以啦。表示之前用了1000004^4的数组一直很奇葩的编译超时，后来直接写成滚动数组就A啦~*

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std;

 

#define MAXN 100001

 

int f[2][4][4][4][4];

 

int n,t=0;

char s[MAXN];

 

int hash(char c){

    switch (c){

        case 'M':return 1;

        case 'F':return 2;

        case 'B':return 3;

    }

}

 

int main(){

    memset(f,0,sizeof(f));

    scanf("%d",&n);

    scanf("%s",&s);

    f[0][hash(s[0])][0][0][0]=f[0][0][0][hash(s[0])][0]=1;

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

        int y=hash(s[i]);

        for (int a=0;a<4;a++){

            for (int b=0;b<4;b++){

                for (int c=0;c<4;c++){

                    for (int d=0;d<4;d++){

                        if (f[t][a][b][c][d]){

                            int x=1+f[t][a][b][c][d];

                            if (a&&a!=y){

                                x++;

                            }

                            if (b&&b!=y&&a!=b&&a){

                                x++;

                            }

                            f[t^1][y][a][c][d]=max(f[t^1][y][a][c][d],x);

                            x=f[t][a][b][c][d]+1;

                            if (c&&c!=y){

                                x++;

                            }

                            if (d&&d!=y&&c!=d&&c){

                                x++;

                            }

                            f[t^1][a][b][y][c]=max(f[t^1][a][b][y][c],x);

                        }

                        f[t][a][b][c][d]=0;

                    }

                }

            }

        }

        t^=1;

    }

    int ans=0;

    for (int a=0;a<4;a++){

        for (int b=0;b<4;b++){

            for (int c=0;c<4;c++){

                for (int d=0;d<4;d++){

                    ans=max(ans,f[t][a][b][c][d]);

                }

            }

        }

    }

    printf("%d\n",ans);

    return 0;

}