CF18E dp

dp[i][j][k]代表第i行为jkjkjkj….
直接转移就好

#include 
#include 
#include 
using namespace std;
char s[505];
int dp[505][26][26],n,m,pre[505][26][26][2];
void dfs(int i, int j, int k)
{if(!i) return;dfs(i-1,pre[i][j][k][0],pre[i][j][k][1]);for(int i=0;iputchar(((i&1)?k:j)+'a');puts("");
}
int main()
{scanf("%d%d",&n,&m);memset(dp,63,sizeof(dp));for(int i=0;i<26;i++)for(int j=0;j<26;j++)dp[0][i][j]=0;for(int i=1;i<=n;i++){scanf("%s",s);for(int j=0;j<26;j++)for(int k=0;k<26;k++){if(j==k)continue;int cnt=0;for(int p=0;p1)?cnt+=(s[p]-'a'!=k):cnt+=(s[p]-'a'!=j);for(int q=0;q<26;q++){if(q==j)continue;for(int w=0;w<26;w++){if(k==w||q==w)continue;if(dp[i-1][q][w]+cnt1][q][w]+cnt;pre[i][j][k][0]=q;pre[i][j][k][1]=w;}}}}}int x=0,y=0,ans=0x3f3f3f3f;for(int i=0;i<26;i++)for(int j=0;j<26;j++)if(ans>dp[n][i][j]){ans=dp[n][i][j],x=i,y=j;}printf("%d\n",dp[n][x][y]);dfs(n,x,y);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！