hdu6017

题意： 话的长度为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)$辣~~ 就是写起来有点恶心