Codeforces Beta Round 18 (Div. 2 Only) E

111
感觉写的好多都是2000分 dp + 路径
这个dp 很明显发现只和 行相关 然后我们发现每行最多俩个 那么肯定就是ababab这种交叉
dp i a b 就是我们第i行选了 a b 交叉的min
转移也是26*26 预处理 cost i a b 作为每行的转移代价即可
最后要注意就是m==1的情况 然后初始化一定要把所有dp [0] 全初始为0

int dp[510][26][26],cost[510][26][26];
void solve(){
    memset(dp,0x3f3f,sizeof dp);
    int n,m;cin>>n>>m;
    int c[n+1][m+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char x;cin>>x;
            c[i][j]=x-'a';
        }
        for(int a=0;a<=25;a++){
            for(int b=0;b<=25;b++){
                int w=0;
                for(int j=1;j<=m;j++){
                    if(j&1)w+=(c[i][j]!=a);
                    else w+=(c[i][j]!=b);
                }
                cost[i][a][b]=w;
            }
        }
    }
    for(int i=0;i<=25;i++){
        for(int j=0;j<=25;j++){
            dp[0][i][j]=0;
        }
    }
    int mn=INF,x,y;
    for(int i=1;i<=n;i++){
        for(int a=0;a<=25;a++){
            for(int b=0;b<=25;b++){
                if(a==b)continue;
                for(int d=0;d<=25;d++){
                    for(int e=0;e<=25;e++){
                        if(d==e)continue;
                        if(m!=1)if(a==d||b==e)continue;
                        if(m==1)if(a==d)continue;
                        dp[i][a][b]=min(dp[i][a][b],dp[i-1][d][e]+cost[i][a][b]);
                        if(i==n&&mn>dp[i][a][b]){
                            mn=min(mn,dp[i][a][b]);
                            x=a,y=b;
                        }
                    }
                }
            }
        }
    }
    cout<<mn<<endl;
    vector<PII>ans(n+1);
    ans[n]={x,y};
    for(int i=n-1;i>=0;i--){
        for(int a=0;a<=25;a++){
            for(int b=0;b<=25;b++){
                if(a==b||a==x||b==y)continue;
                if(dp[i][a][b]==dp[i+1][x][y]-cost[i+1][x][y]){
                    ans[i]={a,b};
                    x=a,y=b;
                    goto out;
                }
            }
        }
        out:1;
    }
    for(int i=1;i<=n;i++){
        auto [x,y]=ans[i];
        for(int j=1;j<=m;j++){
            if(j&1)cout<<(char)(x+'a');
            else cout<<(char)(y+'a');
        }cout<<endl;
    }
}