P1136 迎接儀式
題目描述
LHX教主要來X市指導OI學習工作了。為了迎接教主，在一條道路旁，一群Orz教主er穿著文化衫站在道路兩旁迎接教主，每件文化衫上都印著大字。一旁的Orzer依次擺出“歡迎歡迎歡迎歡迎……”的大字，但是領隊突然發現，另一旁穿著“教”和“主”字文化衫的Orzer卻不太和諧。
為了簡單描述這個不和諧的隊列，我們用“j”替代“教”，“z”替代“主”。而一個“j”與“z”組成的序列則可以描述當前的隊列。為了讓教主看得盡量舒服，你必須調整隊列，使得“jz”子串盡量多。每次調整你可以交換任意位置上的兩個人，也就是序列中任意位置上的兩個字母。而因為教主馬上就來了，時間僅夠最多作K次調整（當然可以調整不滿K次），所以這個問題交給了你。
輸入輸出格式
輸入格式：
?
輸入文件welcome.in的第1行包含2個正整數N與K，表示了序列長度與最多交換次數。
第2行包含了一個長度為N的字符串，字符串僅由字母“j”與字母“z”組成，描述了這個序列。
?
輸出格式：
?
輸出文件welcome.out僅包括一個非負整數，為調整最多K次后最后最多能出現多少個“jz”子串。
?
輸入輸出樣例
5 2 zzzjj
2
說明
【樣例說明】
第1次交換位置1上的z和位置4上的j，變為jzzzj；
第2次交換位置4上的z和位置5上的j，變為jzzjz。
最后的串有2個“jz”子串。
【數據規模與約定】
對于10%的數據，有N≤10；
對于30%的數據，有K≤10；
對于40%的數據，有N≤50；
對于100%的數據，有N≤500，K≤100。
?
?
分析：
參照的洛谷題解
f[i][j][k]表示前i個字符，改變了j個'j'和k個'z'后的“jz”串數。
交換k次，其實意味著k個j變成z，k個z變成j。
所以j和k相等的時候更新答案。
首先相同字符是不用調換的，一個字符最多被調換一次(a<—>b,b<—>c等價于a<—>c)
那么只考慮前兩位，有四種情況（jj,jz,zj,zz）來轉移。
注意初始化！
?
?代碼中四種狀態轉移情況分析一下：
?
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define fo(i,j,k) for(i=j;i<=k;i++) 5 using namespace std; 6 const int mxn=505; 7 char s[mxn]; 8 int dp[mxn][105][105]; //改變了j個j，改變了k個z 9 int n,m,ans; 10 int main() 11 { 12 int i,j,k; 13 scanf("%d%d",&n,&m); 14 scanf("%s",s+1); 15 memset(dp,-0x3f,sizeof dp); 16 dp[0][0][0]=dp[1][0][0]=0; 17 if(s[1]=='z') dp[1][0][1]=0; 18 else dp[1][1][0]=0; 19 fo(i,2,n) 20 fo(j,0,m) 21 fo(k,0,m) 22 { 23 dp[i][j][k]=dp[i-1][j][k]; 24 if(s[i]=='z' && s[i-1]=='j') dp[i][j][k]=max(dp[i][j][k],dp[i-2][j][k]+1); 25 if(s[i]=='z' && s[i-1]=='z' && k) dp[i][j][k]=max(dp[i][j][k],dp[i-2][j][k-1]+1); 26 if(s[i]=='j' && s[i-1]=='j' && j) dp[i][j][k]=max(dp[i][j][k],dp[i-2][j-1][k]+1); 27 if(s[i]=='j' && s[i-1]=='z' && j && k) dp[i][j][k]=max(dp[i][j][k],dp[i-2][j-1][k-1]+1); 28 if(j==k) ans=max(ans,dp[i][j][k]); 29 } 30 printf("%d\n",ans); 31 return 0; 32 }
?
