2525 小b的字符串

給定一個由?ABCABC?三種字符構成的字符串，問最少改動多少個位置的字符，

使得最終的字符串滿足任意兩個相鄰的字符都不同。

字符串長度?≤106≤106

輸入

一行一個字符串。

輸出

一行一個整數表示答案。

輸入樣例

ABCBA

輸出樣例

0

思路：

? ? ? ? 這題怎么搞都能過，dp狀態設為選或者不選，或者設為A\B\C三種都行，因為

兩兩不同有高達6中方案，所以選或者不選的dp方案沒有后效性。

? ? ? ? 模擬的話就是找連續的相同字母，并在每一段相同字母區間上更新答案。

第二種dp代碼實現

（寫的略復雜，有題解用str[i]-'A'代替了無數分支）：

#include<iostream> #include<string.h> #include<stdio.h> #include<math.h> #include<set> #include<algorithm> #define LL long long #define INF 0x3f3f3f3f using namespace std; const int N=2e5+100; const int M=4e5+100; int dp[N][3]; int main(){string str;int len;while(cin>>str){memset(dp,INF,sizeof(dp));len=str.length();if(str[0]=='A'){dp[0][0]=0;dp[0][1]=dp[0][2]=1;}else if(str[0]=='B'){dp[0][1]=0;dp[0][0]=dp[0][2]=1;}else{dp[0][2]=0;dp[0][1]=dp[0][0]=1;}for(int i=1;i<len;i++){if(str[i]=='A'){dp[i][0]=min(dp[i-1][1],dp[i-1][2]);dp[i][1]=min(dp[i-1][0],dp[i-1][2])+1;dp[i][2]=min(dp[i-1][0],dp[i-1][1])+1;}else if(str[i]=='B'){dp[i][0]=min(dp[i-1][1],dp[i-1][2])+1;dp[i][1]=min(dp[i-1][0],dp[i-1][2]);dp[i][2]=min(dp[i-1][0],dp[i-1][1])+1;}else{dp[i][0]=min(dp[i-1][1],dp[i-1][2])+1; dp[i][1]=min(dp[i-1][0],dp[i-1][2])+1;dp[i][2]=min(dp[i-1][0],dp[i-1][1]);}}cout<<min(min(dp[len-1][0],dp[len-1][1]),dp[len-1][2])<<endl;}return 0;}

THE END；

總結

以上是生活随笔為你收集整理的2525 小b的字符串 （字符串思维、dp、胡搞都能过）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。