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;
}
}