首页 > 代码库 > CodeForces 18E Flag 2 dp
CodeForces 18E Flag 2 dp
题目链接:点击打开链接
#include<stdio.h> #include<iostream> #include<string.h> #include<set> #include<vector> #include<map> #include<math.h> #include<queue> #include<string> #include<stdlib.h> #include<algorithm> using namespace std; #define N 505 #define inf 1000000009 #define siz 26 char s[N][N]; int n, m; int dp[N][siz][siz]; int a_path[N][siz][siz], b_path[N][siz][siz]; int cost(int x, int a, int b){ a += 'a'; b += 'a'; int ans = 0; for(int i = 0; i < n; i++) if(i&1) ans += (a!=s[x][i]); else ans += (b!=s[x][i]); return ans; } void put(int z, int x, int y){ if(z)put(z-1, a_path[z][x][y], b_path[z][x][y]); for(int i = 0; i < n; i++) if(i&1)printf("%c",x+'a'); else printf("%c",y+'a'); puts(""); } int main(){ while(cin>>m>>n) { for(int i = 0; i < m; i++)scanf("%s",s[i]); for(int i = 0; i < siz; i++) { for(int j = 0; j < siz; j++) if(i==j)dp[0][i][j] = inf; else dp[0][i][j] = cost(0,i,j); } for(int i = 1; i < m; i++) { for(int A = 0; A < siz; A++) for(int B = 0; B < siz; B++) { if(A == B)continue; int cur = cost(i, A, B); int mid, minn = inf, x = -1, y = -1; for(int a = 0; a < siz; a++) for(int b = 0; b < siz; b++) { if(a == A || b == B || a==b)continue; if(minn > dp[i-1][a][b]) minn = dp[i-1][a][b],x=a,y=b; } dp[i][A][B] = minn + cur; a_path[i][A][B] = x; b_path[i][A][B] = y; } } int minn = inf, x, y; for(int a = 0; a < siz; a++) { for(int b = 0; b < siz; b++) { if(a==b)continue; if(minn>dp[m-1][a][b]) minn = dp[m-1][a][b], x = a, y = b; } } cout<<dp[m-1][x][y]<<endl; put(m-1,x,y); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。