codeforces 18E Flag 2 (dp)

제목:
문자열의 행렬을 보여 줍니다. 이제 이런 규칙에 따라 변환해야 합니다.
1. 줄마다 두 개의 자모만 있을 수 있다.(열당 여러 글자)
2. 임의로 인접한 자모는 같을 수 없다.
최소한의 조작수를 구하고 변환된 행렬을 인쇄해야 합니다.
문제 풀이:
이러한 요구를 분석하면 한 줄에서 반드시 이런 형식이어야 조건을 만족시킬 수 있다는 것을 발견할 수 있다. 그것이 바로 ABABABAB...
그러면 우리는 상태 dp[i][A][B]를 정의한다. i행은 알파벳 A를 사용했고 B라는 두 알파벳의 구성 형식인 ABABABA를 사용했다.(선후 순서가 있는) 그리고 줄dp를 누르면 된다.가까스로 지내다.

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
//typedef long long lld;
const int oo=0x3f3f3f3f;
//const lld OO=1LL<<61;
const int MOD=(1e9)+7;
const int maxn=505;
int dp[maxn][26][26];
struct
{
    int A,B;
}pre[maxn][26][26];
char maze[maxn][maxn];
int n,m;

int cost(int i,int a,int b)
{
    char A=a+'a',B=b+'a';
    int ans=0;
    for(int j=1;j<=m;j++)
    {
        if(j&1) ans+=(maze[i][j]!=A);
        else ans+=(maze[i][j]!=B);
    }
    return ans;
}

void DP()
{
    memset(dp,0x3f,sizeof dp);
    for(int A=0;A<26;A++)
        for(int B=0;B<26;B++)
            if(A!=B)
                dp[1][A][B]=cost(1,A,B);
    for(int i=2;i<=n;i++)
    {
        for(int A=0;A<26;A++)
        {
            for(int B=0;B<26;B++)
            {
                if(A==B)continue;
                int c=cost(i,A,B);
                for(int a=0;a<26;a++)
                {
                    if(a==A)continue;
                    for(int b=0;b<26;b++)
                    {
                        if(b==B)continue;
                        if(a==b)continue;
                        if(dp[i-1][a][b]==oo)continue;
                        if(dp[i][A][B]>dp[i-1][a][b]+c)
                        {
                            dp[i][A][B]=dp[i-1][a][b]+c;
                            pre[i][A][B].A=a;
                            pre[i][A][B].B=b;
                        }
                    }
                }
            }
        }
    }

    int ans=oo,A,B;
    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];
                A=i;
                B=j;
            }
    printf("%d
",ans);
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=m;j++)
        {
            if(j&1) maze[i][j]=A+'a';
            else maze[i][j]=B+'a';
        }
        int a=A,b=B;
        A=pre[i][a][b].A;
        B=pre[i][a][b].B;
    }
    for(int i=1;i<=n;i++)
        printf("%s
",maze[i]+1);
}

int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%s",maze[i]+1);
        DP();
    }
    return 0;
}
/**

3 4
aaaa
bbbb
cccc

3 3
aba
aba
zzz

*/