P1136 迎接儀式

題目描述

LHX教主要來X市指導(dǎo)OI學(xué)習(xí)工作了。為了迎接教主，在一條道路旁，一群Orz教主er穿著文化衫站在道路兩旁迎接教主，每件文化衫上都印著大字。一旁的Orzer依次擺出“歡迎歡迎歡迎歡迎……”的大字，但是領(lǐng)隊突然發(fā)現(xiàn)，另一旁穿著“教”和“主”字文化衫的Orzer卻不太和諧。

為了簡單描述這個不和諧的隊列，我們用“\(j\)”替代“教”，“\(z\)”替代“主”。而一個“\(j\)”與“\(z\)”組成的序列則可以描述當(dāng)前的隊列。為了讓教主看得盡量舒服，你必須調(diào)整隊列，使得“\(jz\)”子串盡量多。每次調(diào)整你可以交換任意位置上的兩個人，也就是序列中任意位置上的兩個字母。而因為教主馬上就來了，時間僅夠最多作\(K\)次調(diào)整（當(dāng)然可以調(diào)整不滿\(K\)次），所以這個問題交給了你。

輸入輸出格式

輸入格式：

第一行包含\(2\)個正整數(shù)\(N\)與\(K\)，表示了序列長度與最多交換次數(shù)。

第二行包含了一個長度為\(N\)的字符串，字符串僅由字母“\(j\)”與字母“\(z\)”組成，描述了這個序列。

輸出格式：

一個非負整數(shù)，為調(diào)整最多\(K\)次后最后最多能出現(xiàn)多少個“\(jz\)”子串。

數(shù)據(jù)規(guī)模與約定

對于\(10\%\)的數(shù)據(jù)，有\(N≤10\)；

對于\(30\%\)的數(shù)據(jù)，有\(K≤10\)；

對于\(40\%\)的數(shù)據(jù)，有\(N≤50\)；

對于\(100\%\)的數(shù)據(jù)，有\(N≤500,K≤100\)。

---

神題啊，膜拜膜拜~~

看起來就是地痞，考慮一下如何把狀態(tài)都給丟進去

因為一次涉及兩個地方的位置，所以我們很難把這樣的狀態(tài)準(zhǔn)確表示。

我們可以考慮先找一些特殊的突破點或者顯然成立的貪心性質(zhì)

說到特殊，這個序列的字符集只有\(2\)

說道性質(zhì)，很顯然，一個位置不會被改兩次，兩個一樣字符的不會被改。

以上是我開了上帝視角得出的，事實上，我們可能可以想到它們，但是它們不一定會真正啟發(fā)到我們

還是要看做題積累的經(jīng)驗

下面上正解：

\(dp_{i,j,k}\)代表在位置\(i\),\('j'\)這個字符被交換過\(j\)次，\('z'\)這個字符被交換過\(k\)次

請注意，這個交換是存在匹配的，但我們只管匹配，并不在乎具體誰和誰交換過

如果你沒能理解上面這句話，請看看狀態(tài)轉(zhuǎn)移方程

因為一個匹配需要兩個字符，所以我們從\(當(dāng)前位置-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]);

格外注意一下答案更新的地方，相等時更新代表什么，其實就是代表匹配上去了，這些東西都在互有交換，但現(xiàn)在交換次數(shù)一樣了，所以我們可以更新答案

值得一提的是，我們其實并沒有單以位置劃分狀態(tài)，可以注意到，匹配的位置是前后都有的，我們是把位置和交換的狀態(tài)放在一起，才做到了無后效性

個人拙見，如有錯誤，煩請?zhí)岢?/p>

---

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

轉(zhuǎn)載于:https://www.cnblogs.com/butterflydew/p/9594426.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P1136 迎接仪式 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。