C 被涂色的作文纸

区间dp，设dp[i][j][k][l]为区间[i,j]内且把左端点涂成k，右端点涂成l的最大分数。状态转移方程见代码

#include<bits/stdc++.h>
using namespace std;
int n,a[1005],b[1005],c[1005],dp[1005][1005][2][2];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(i==j){
                dp[i][j][0][0]=a[i];
                dp[i][j][1][1]=b[i];
            }
            else{
                dp[i][j][0][0]=max(max(dp[i+1][j][1][0]+a[i],dp[i+1][j][0][0]+a[i]+c[i]+c[i+1]),max(dp[i][j-1][0][1]+a[j],dp[i][j-1][0][0]+a[j]+c[j]+c[j-1]));
                dp[i][j][1][0]=max(max(dp[i+1][j][1][0]+b[i]+c[i]+c[i+1],dp[i+1][j][0][0]+b[i]),max(dp[i][j-1][1][1]+a[j],dp[i][j-1][1][0]+a[j]+c[j]+c[j-1]));
                dp[i][j][0][1]=max(max(dp[i+1][j][1][1]+a[i],dp[i+1][j][0][1]+a[i]+c[i]+c[i+1]),max(dp[i][j-1][0][1]+b[j]+c[j]+c[j-1],dp[i][j-1][0][0]+b[j]));
                dp[i][j][1][1]=max(max(dp[i+1][j][1][1]+b[i]+c[i]+c[i+1],dp[i+1][j][0][1]+b[i]),max(dp[i][j-1][1][1]+b[j]+c[j]+c[j-1],dp[i][j-1][1][0]+b[j]));
            }
        }
    }
    cout<<max(max(dp[1][n][0][1],dp[1][n][1][1]),max(dp[1][n][1][0],dp[1][n][0][0]));
    return 0;
}