题目链接：
codeforces 219C
题目大意：
给出一个字符串，只包含k种字符，问最少修改多少个字符（不增长新的种类）能够得到一个新的字符串，这个字符串满足相邻的字符没有相同的。
题目分析：然后这样直接做的复杂度是,只是常熟略大，几百毫秒过的。 AC代码：;int dp[MAX][30];int lef[30];int rig[30];char s[MAX];int a[MAX];int n,k;int main ( ){while ( ~scanf ( “%d%d” , &n , &k ) ){scanf ( “%s” , s+1 );for ( int i = 1 ; i <= n ; i++ )a[i] = s[i]-‘A’;memset ( dp , 0x3f , sizeof ( dp ) );for ( int i = 0 ; i < k; i++ )if ( i == a[1] ) dp[1][i] = 0;else dp[1][i] = 1;lef[0] = dp[1][0];for ( int i = 1; i < k; i++ )lef[i] = min ( lef[i-1] , dp[1][i] );rig[k-1] = dp[1][k-1];for ( int i = k-2 ; i >= 0 ; i– )rig[i] = min ( rig[i+1] , dp[1][i] );for ( int i = 2 ; i <= n ; i++ ){for ( int j = 0 ; j < k; j++ ){int temp;if ( j == 0 ) temp = rig[j+1];else if ( j == k-1 ) temp = lef[j-1];else temp = min ( lef[j-1] , rig[j+1] );if ( j == a[i] ) dp[i][j] = temp;else dp[i][j] = temp+1;}lef[0] = dp[i][0];for ( int j = 1 ; j < k ; j++ )lef[j] = min ( lef[j-1] , dp[i][j] );rig[k-1] = dp[i][k-1];for ( int j = k-2 ; j >= 0 ; j– )rig[j] = min ( rig[j+1] , dp[i][j] );}int minn = 1<<29;for ( int i = 0 ; i < k; i++ )minn = min ( minn , dp[n][i] );printf ( “%d\n” , minn );stack<char> ans;int kk = -1;for ( int i = n ; i > 0 ; i– )for ( int j = 0 ; j < k; j++ ){if ( j != kk && dp[i][j] == minn ){ans.push ( (char)(‘A’+j) );if ( j != a[i] ) minn–;kk = j;break;}}while ( !ans.empty() ){printf ( “%c” , ans.top() );ans.pop();}puts ( “” );}}
，当你感到悲哀痛苦时，最好是去学些什么东西。
