Link:

Solution:

为了使状态包含每个节点前所有必须的信息：

设$dp[i][a1][a2][b1][b2]$为配送到第$i$个，一厂前两个为$a1,a2$，二厂前两个为$b1,b2$时的最大权值，

每次向一厂添加/二厂添加转移。

 

要使用滚动数组，注意对每种情况权值的计算。

Code:

#include 
     
      using namespace std;int dp[3][4][4][4][4],n,res=0,cur,pre;int get_type(){    char ch=getchar();    while(ch!='M' && ch!='F' && ch!='B') ch=getchar();    if(ch=='M') return 1;    else if(ch=='F') return 2;    else return 3;}int cal(int a,int b,int c){    int ret=1;    if(b && b!=c) ret++;    if(a && a!=b && a!=c) ret++;    return ret;}int main(){    scanf("%d",&n);    memset(dp,-1,sizeof(dp));    cur=1;dp[pre][0][0][0][0]=0;        for(int i=0;i
     

 

Review:

每次要想清楚循环的边界，

这里一开始不到4个时无法填充$a1,a2,b1,b2$所有状态，因此要从'0'开始循环