題意： 話的長度為n，語句里的字符不是2就是3。 呃喵的智力非常有限，只有m點。她每次操作可以交換兩個相鄰的字符，然而代價是智力-2。 現(xiàn)在問你，在使得自己智力不降為負(fù)數(shù)的條件下，呃喵最多能使這個字符串中有多少個子串”233”呢？ 如”2333”中有一個”233”，”232323”中沒有”233” 1 <= n <= 100, 0 <= m <= 100

題解： 一看到正解是O(n4)$O(n^4)$的而我是O(n3)$O(n^3)$的嚇得我趕緊寫一篇題解 首先要發(fā)現(xiàn)兩個性質(zhì) 1、所有的操作方式都能只用前移完成 2、交換后同種字符間的相對順序不會改變 考慮dp，根據(jù)性質(zhì)1轉(zhuǎn)移時可以只用位置i前移得到所有狀態(tài) 最暴力的狀態(tài)是f[i][s][k]，表示處理了前i個位置，串長的樣子是s，得到k個233最少交換幾次。 根據(jù)性質(zhì)2，假設(shè)s[i+1]為2，那他最終移動到的位置不會比上一個2要前，所以我們不需要記錄整個串長什么樣子，只需要記錄上一個2出現(xiàn)的位置即可。3也是同理。 那么狀態(tài)就變成了f[i][j1][j2][k]，j1和j2分別表示2和3上一次出現(xiàn)位置。再觀察發(fā)現(xiàn)j1和j2必定有一個是i，所以可以省掉一維。 最終狀態(tài)就是f[i][j][k][o1][o2]。表示考慮了前i位，上一個與第i位不同的字符在位置j，匹配出k個233，第i位為o1，第j位為o2最少交換幾次。o1，o2的取值為0,1,2。0表示這是一個2。1表示這是一個3，并且在他后面加一個3可以貢獻(xiàn)答案。2就表示不能貢獻(xiàn)答案的3。 考慮轉(zhuǎn)移，枚舉新加入的位轉(zhuǎn)移到哪個位置很容易，但是O(n4)$O(n^4)$不穩(wěn)啊。。 觀察一下，發(fā)現(xiàn)枚舉位置轉(zhuǎn)移一個非常辣雞的地方在于，他做了很多重復(fù)的轉(zhuǎn)移，比如： 枚舉i+1這個2要轉(zhuǎn)移到中間那一段時，轉(zhuǎn)移的狀態(tài)其實都是f[i+1][j1][k+1][2][0]。而且考慮一下把這個2換到前面，破壞一個答案肯定不是最優(yōu)的。所以特殊的轉(zhuǎn)移只有換一次換到位置i。而中間一段同樣的轉(zhuǎn)移，用個數(shù)組記錄，最后掃一遍就好了。 分析一下3的轉(zhuǎn)移，也有類似的浪費(fèi)，同樣的方法處理即可。 于是復(fù)雜度就將到O(n3)$O(n^3)$辣~~ 就是寫起來有點惡心