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

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