P1136 迎接儀式
題目描述
LHX教主要來X市指導OI學習工作了。為了迎接教主，在一條道路旁，一群Orz教主er穿著文化衫站在道路兩旁迎接教主，每件文化衫上都印著大字。一旁的Orzer依次擺出“歡迎歡迎歡迎歡迎……”的大字，但是領隊突然發現，另一旁穿著“教”和“主”字文化衫的Orzer卻不太和諧。
為了簡單描述這個不和諧的隊列，我們用“\(j\)”替代“教”，“\(z\)”替代“主”。而一個“\(j\)”與“\(z\)”組成的序列則可以描述當前的隊列。為了讓教主看得盡量舒服，你必須調整隊列，使得“\(jz\)”子串盡量多。每次調整你可以交換任意位置上的兩個人，也就是序列中任意位置上的兩個字母。而因為教主馬上就來了，時間僅夠最多作\(K\)次調整（當然可以調整不滿\(K\)次），所以這個問題交給了你。
輸入輸出格式
輸入格式：
第一行包含\(2\)個正整數\(N\)與\(K\)，表示了序列長度與最多交換次數。
第二行包含了一個長度為\(N\)的字符串，字符串僅由字母“\(j\)”與字母“\(z\)”組成，描述了這個序列。
輸出格式：
一個非負整數，為調整最多\(K\)次后最后最多能出現多少個“\(jz\)”子串。
數據規模與約定
對于\(10\%\)的數據，有\(N≤10\)；
對于\(30\%\)的數據，有\(K≤10\)；
對于\(40\%\)的數據，有\(N≤50\)；
對于\(100\%\)的數據，有\(N≤500,K≤100\)。
神題啊，膜拜膜拜~~
看起來就是地痞，考慮一下如何把狀態都給丟進去
因為一次涉及兩個地方的位置，所以我們很難把這樣的狀態準確表示。
我們可以考慮先找一些特殊的突破點或者顯然成立的貪心性質
說到特殊，這個序列的字符集只有\(2\)
說道性質，很顯然，一個位置不會被改兩次，兩個一樣字符的不會被改。
以上是我開了上帝視角得出的，事實上，我們可能可以想到它們，但是它們不一定會真正啟發到我們
還是要看做題積累的經驗
下面上正解：
\(dp_{i,j,k}\)代表在位置\(i\),\('j'\)這個字符被交換過\(j\)次，\('z'\)這個字符被交換過\(k\)次
請注意，這個交換是存在匹配的，但我們只管匹配，并不在乎具體誰和誰交換過
如果你沒能理解上面這句話，請看看狀態轉移方程
因為一個匹配需要兩個字符，所以我們從\(當前位置-2\)的地方之前進行更新
dp[i][j][k]=dp[i-1][j][k];
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);
if(s[i]=='z'&&s[i-1]=='j')dp[i][j][k]=max(dp[i][j][k],dp[i-2][j][k]+1);
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);
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);
if(j==k) ans=max(ans,dp[i][j][k]);格外注意一下答案更新的地方，相等時更新代表什么，其實就是代表匹配上去了，這些東西都在互有交換，但現在交換次數一樣了，所以我們可以更新答案
值得一提的是，我們其實并沒有單以位置劃分狀態，可以注意到，匹配的位置是前后都有的，我們是把位置和交換的狀態放在一起，才做到了無后效性
個人拙見，如有錯誤，煩請提出
Code:
#include <cstdio>
#include <cstring>
int max(int x,int y){return x>y?x:y;}
const int N=502;
int dp[N][103][103],n,m,ans;
char s[N];
int main()
{scanf("%d%d%s",&n,&m,s+1);memset(dp,-0x3f,sizeof(dp));dp[0][0][0]=dp[1][0][0]=dp[1][s[1]=='j'][s[1]=='z']=0;for(int i=2;i<=n;i++)for(int j=0;j<=m;j++)for(int k=0;k<=m;k++){dp[i][j][k]=dp[i-1][j][k];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);else if(s[i]=='z'&&s[i-1]=='j')dp[i][j][k]=max(dp[i][j][k],dp[i-2][j][k]+1);else 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);else 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);if(j==k) ans=max(ans,dp[i][j][k]);}printf("%d\n",ans);return 0;
}
2018.9.5
)
