C. Color Stripe
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A colored stripe is represented by a horizontal row of n square cells, each cell is pained one of k colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to k to repaint the cells.

Input

The first input line contains two integers n and k (1 ≤ n ≤ 5·105; 2 ≤ k ≤ 26). The second line contains n uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first k English letters may be used. Each letter represents the color of the corresponding cell of the stripe.

Output

Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.

Examples
input 
6 3
ABBACC
output 
2
ABCACA
input 
3 2
BBB
output 
1
BAB

题意: 长度n,可用前k种字母.串s相邻的两个字母都不相同,问最少的需要改变几次.


思路:dp[i][j]定义为: 将第i个字母变成j至少需要修改的次数

dp[i][j]= Min(dp[i][j],dp[i-1][t(t!=j)]+ s[i]-'A'==j ? 0 : 1  );


于是我们求的是dp[n][(0~k)]的最小值  最小的哪个k就是最后一个字母-'A'

路径用一个pre数组记录


#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define bug1 cout <<"bug1"<<endl
#define bug2 cout <<"bug2"<<endl
#define bug3 cout <<"bug3"<<endl
using namespace std;
typedef long long ll;

const int MAX_N=5e5+50;
char s[MAX_N];
int dp[MAX_N][28];
int pre[MAX_N][28];
int ans[MAX_N];

int main(void){
    int n,k;
    cin >> n>>k;
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
        for(int j=0;j<k;j++)    dp[i][j]=INF;
    for(int i=1;i<=n;i++){
        for(int j=0;j<k;j++){
            for(int t=0;t<k;t++){
                if(t==j)    continue;
                if(s[i]-'A'==j){
                    if(dp[i-1][t]<dp[i][j]) dp[i][j]=dp[i-1][t],pre[i][j]=t;
                }
                else{
                    if(dp[i-1][t]+1<dp[i][j]) dp[i][j]=dp[i-1][t]+1,pre[i][j]=t;
                }
            }
        }
    }
    int mmin=INF,index;
    for(int i=0;i<k;i++)
        if(dp[n][i]<mmin)   mmin=dp[n][i],index=i;
    cout << mmin << endl;
    int nn=n;
    ans[n]=index+'A';
    while(n){
        ans[n-1]=pre[n][index]+'A';
        index=ans[n-1]-'A';
        n--;
    }
    for(int i=1;i<=nn;i++)  printf("%c",ans[i]);
    printf("\n");
}