分类： 线性DP

题目链接

题意：给定一个字符串S，长度为n≤100，然后定义一个操作是将S的一个含有L个字符的子序列看作一个字符串插入到一个无重复元素的set里，每次操作的cost是(n-L)，然后问对于给定的k（k最大可取1e12），最少需要多少总cost才能使得set的元素个数达到k。难度2200分，有点虚高其实，不过还是不那么好想的。用先后顺序去重是关键idea。

做这种代码段但是考思维的小题还是挺有意思的。。。。

这题是mike出的，感觉挺经典那种。他有一个easy version是k≤100，这个要求的话就很松了，mike的题解直接用了一种及其暴力的方法：把每个subsequence当作一个点，相差一个字符的点之间连边建图，直接暴力跑bfs。。。这个肯定是个时间和空间复杂度都爆炸的算法，但是k≤100的时候很快就能搜到，只要及时跳出bfs就可以了。

这个H版本要求k最大可能是1e12，这就不能再那么操作了。首先写几个简单的样例就可以发现这个主要跟unique的子序列的长度和数量有关系，如果我们能求出来对应于某一长度j的unique子序列有多少个，那就可以解决这个问题了。这个就是一个引导方向，可以先试着设dp[i][j]表示以i为结尾的长度为j的子序列个数。状态定义好了之后考虑转移，按照大问题转化为小问题的思想，dp[i][j]表示的以i结尾的unique子序列，那么如果去掉s[i]之后这些子序列一定是互不相同的长度为j-1的子序列，数量没有多也没有少。所以现在就是要考虑怎么算出来前i-1个字符构成的子序列里面有多少个了。利用已经计算得得信息，这个一定是某些dp[pos][j-1]之和，但是有一种情况的是不同的pos对应的子串可能一样，所以这个题目最精彩的部分就来了，每次在相同的字符中选取最靠后的作为计算点。第一这样起码不会比选择前面的点坏，如果前面的点能凑成q个子序列那么后面的点凑成的相同长度的子序列只会多不会少，即不漏；第二这个就避免了重复计算的现象，不重不漏即为正确的dp转移。所以如果用\[lst[i][w]\]表示前i个字符里面字符为\[‘a’+w (w \in [0,25])\],可以写出来状态转移方程为

\[dp[i][j]=\sum_{w=0}^{25} dp[lst[i-1][w]][j-1]\]

至于lst显然很简单的一个dp就推出来了lst[i][j]=((int)(s[i]-‘a’)==j)?i:lst[i-1][j];
继续阅读“[DP][思维][×] codeforces 1183H Subsequences (hard version)”