矿工配餐

题目大意
有两个矿井及N辆矿车，每个矿工的产煤量与其最后三顿饭的种类数有关。求最大产煤量。

算法
DP，f[i][j1][j2][j3][j4][j5]表示处理到第i辆，第一个矿井前两天吃的是j1，j2，第二个矿井前两天吃的是j3，j4。

但是空间只有18MB，所以我们采用滚动数组

代码

#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
#define max(a,b) ((a)>(b))?(a):(b)
#define min(a,b) ((a)<(b))?(a):(b)
#define _f(i,a,b) for(int i=a;i<=b;i++)
unsigned char f[100001]={0};
int x[4][4][4][4],y[4][4][4][4];
int main(){
    int n;
    scanf("%d\n",&n);
    for(int i=1;i<=n;i++){
        char ch=getchar();
        switch(ch){
            case 'M':
                f[i]++;
            case 'F':
                f[i]++;
            case 'B':
                f[i]++;
        }
    }
    memset(x,0,sizeof(x));
    for(int i=n;i>=1;i--){
        memset(y,0,sizeof(y));
        _f(j1,0,3)_f(j2,0,3)_f(j3,0,3)_f(j4,0,3){
            if((j1 && !j2)||(j3 && !j4))
                continue;
            int _1,_2;
            if((!j1 && !j2)||(!j1 && j2==f[i])||
                (j1==j2 && j2==f[i]))
                _1=1;
            else if(j1!=j2 && j2!=f[i] && j1!=f[i] && j1 && j2)
                _1=3;
            else
                _1=2;
            if((!j3 && !j4)||(!j3 && j4==f[i])||
                (j3==j4 && j4==f[i]))
                _2=1;
            else if(j3!=j4 && j4!=f[i] && j3!=f[i] && j3 && j4)
                _2=3;
            else
                _2=2;
            y[j1][j2][j3][j4]=max(x[j2][f[i]][j3][j4]+_1,
                x[j1][j2][j4][f[i]]+_2);
        }
        swap(x,y);
    }
    printf("%d\n",x[0][0][0][0]);
    return 0;
}