相当于noip前两题难度的ioi题。。。。。。。。

　　还是挺好想的。。。算是状压一下？。。。两个二进制位可以表示三种食物或者没有，所以用四个二进制位表示某个煤矿最近两餐的情况。。。

　　先把各种情况加上各种食物后的产出与新情况预处理出来吧。（如果两餐开两维的话似乎不太好预处理）

　　f[i][j][k]表示前i辆车，两个煤矿最近两餐情况分别为j和k时的最大产出。i那维滚动一下

　　感觉要注意的就是，两餐的情况是有非法情况的（前一餐吃了，后一餐不吃）；还有就是有的情况可能用目前的食物凑不出来。。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int inf=1000233333; 6 int f[2][16][16],v[16][4],turn[16][4],num1[16]; 7 int mp[16],kind; 8 int i,j,k,n,m,x,now,pre,ans; 9 char rx;10 11 inline int max(int a,int b){
    return a
         
          3)+((i&3)>0),i++)if(!(i>3&&!(i&3))){16         mp[++kind]=i;17         for(j=1;j<4;j++){18             int x1=i>>2,x2=i&3;19             v[i][j]=(j!=x1&&j!=x2)+(x1||x2)+(x1&&x2&&x1!=x2);20             turn[i][j]=(x2<<2)|j;21 22         }23     }24     scanf("%d",&n);25     memset(f[0],150,sizeof(f[0])),f[0][0][0]=0;26     for(i=now=1,pre=0;i<=n;i++,swap(now,pre)){27         memset(f[now],150,sizeof(f[now]));28         for(rx=getchar();rx<'A'||rx>'Z';rx=getchar());29         if(rx=='M')x=1;else x=rx=='F'?2:3;30         for(j=1;j<=kind;j++)for(k=1;k<=kind;k++)31             f[now][turn[mp[j]][x]][mp[k]]=max(f[now][turn[mp[j]][x]][mp[k]],f[pre][mp[j]][mp[k]]+v[mp[j]][x]),32             f[now][mp[j]][turn[mp[k]][x]]=max(f[now][mp[j]][turn[mp[k]][x]],f[pre][mp[j]][mp[k]]+v[mp[k]][x]);33     }34     for(j=1;j<=kind;j++)for(k=1;k<=kind;k++)ans=max(ans,f[pre][mp[j]][mp[k]]);35     printf("%d\n",ans);36     return 0;37 }