序列型线性dp
TODO
序列型线性dp
问题定义
此处的“序列型线性dp”，指的是以最长上升子序列（LIS）为代表的dp类问题（LIS问题应该都比较熟悉了吧）。
此类问题会给定一个序列，需要我们选出一个子序列或者去掉一些数，使得取出的部分或者剩下的部分，元素与元素之间满足一定的性质，且“评分最高”。
仍然以最长上升子序列问题为例子，根据上一段的描述，我们可以发现这个问题需要我们选出一些数，使得它们具有单调递增的性质，且选出来的数的个数作为评分，希望最大化这个评分。
在这里插一层楼，记录一下LIS问题的贪心解法。
假设现在分析到了
a[i]， 我们不妨看一看之前的子序列们的情况，显然，如果前面有一个子序列以x结尾，且x >= a[i]，那么把x替换成a[i]不会使得答案更差。如果a[i]比所有的结尾都大，那么可以把a[i]连接到最长的那个子序列后面。下面我们证明这种贪心的做法构造出的最长上升子序列的长度
ans和实际的最长上升子序列max的长度是相等的。利用判断两个数相等的策略，只要证明ans <= max且ans >= max即可。显然有ans <= max，只要证明ans >= max即可。我们在这里使用调整法，考虑如何把最优解去调整成贪心解。假设最优解不是按照我们的贪心策略来的，那么最优解的最长上升子序列中，我们考虑这两个策略的第一个不同的元素，由于最优解不是用贪心策略得到的，假设这个位置贪心解是
x，最优解是y，前一个数是z，那么x >= z且y >= z且x <= y，显然，如果把最优解中这里的y换成x，那么最优解中后面的部分不需要改变，仍然是一个上升子序列，且是最长的。一直这样做下去，我们可以把最优解调整成贪心解，且二者长度相同。所以贪心解就是其中一个最优解。考虑需要用几个单调不增的子序列才能覆盖整个序列，我们可以采用类似的贪心思路：对于一个数
a[i]，如果前面有比它大的，那么就接到比它大的最小的数后面，否则就单开一个序列。假设贪心出来发现需要的子序列个数是ans，最优解是min，那么我们也可以从左往右去找到第一个贪心解与最优解不同的位置，那么在最优解中，这个数后面跟着的子序列肯定可以接到前面任何大于等于这个数的数后面，特别的，可以接到比这个数大的最小的数后面，转化为贪心解，结果不会变差，一直这样做下去会发现贪心解其实确实是一个最优解。
建模与求解方法归纳
通过总结可以发现，此类问题拥有类似的状态设计方式，下面我们用几个问题分析一下此类问题的建模方式。
这个是夏季每日一题第三天的题目，题目大意是有一个序列，序列中所有的元素都在1-n之间，可以把这些元素的值看成图的结点号。然后给出了含有n个点的完全图的所有边的边权。接下来，题目希望我们按照序列描述的结点顺序沿着边走，可以途中跳过至多k次结点，问这样走完边权之和最大是多少。
这个问题相当于要我们选出一些数，然后按照顺序去走图（性质），计算边权之和（评分），希望边权之和最大。
状态设计上，可以考虑设dp[i][j]为以序列中第i个结点结尾的，之前跳过过j个结点的走法集合中，经过的边权之和最大的那个走法的边权和。考虑其能够从哪些类状态转移过来，容易发现似乎小于i的序列中的前面那些结点都有可能转移过来，类似朴素的LIS求法的转移。不过这里有跳过次数的限制，所以j不能超过k。
状态转移方程为：dp[i][j] = max(dp[l][j - (i - l - 1)] + w[a[l]][a[i]]), l < i j - (i - l - 1) >= 0
考虑一下初始化，dp[1][0] = dp[1][1] = 0无疑问，dp[1][i] i > 1 都没意义，应该设成负无穷大。至于其他的dp数组，也设为负无穷大即可，不影响计算，这样边界条件就搞好了。
对于最后要求的答案，由于非法的状态我们不做转移，且跳跃操作可以跳过任何结点，所以我们可以求dp数组中的最大值，将其作为答案。这样就可以写代码了。
前女友在去年同期曾经给我发过一个类似的dp问题，可是我自己做不出来，还因为“简单”这个词和她吵了一架，呵呵，可能当时我还是太弱了吧。