【每日一题】3月27日题目精讲 前缀和、动态规划

题号 NC15553

名称 数学考试

来源 2018年长沙理工大学第十三届程序设计竞赛

希望大家尝试思考并解决这个三个问题。

————————————————以下是本题思路——————————————

因为长度已知，最暴力的办法肯定是直接枚举两个子区间的起点，然后求和，复杂度。
连续区间求和可以用前缀和来优化，即用 表示数列前 个数字的和，那么，而区间 的和则可以表示为。这样优化之后就不用遍历求和了直接算就好，时间复杂度变为
实际上我们根本不用枚举右边子区间的起点，因为如果我们的选择的左边这个区间是 的话，右边的区间一定是 右边的所以长度为 的区间里面和最大的那个，这个只需要从右往左扫描一遍就可以维护出来——如果我们用 表示 右边的所有长度为 的区间的和的最大值，那么（要么是i+1右边长度为 的区间的最大值，要么是从 开始向右长度为 的区间）。
这样子了。

————————————————以下是变形一的思路——————————————

变形一：不限制长度——在一个数列里找两个不相交区间使得他们权值和最大
如果思路还和刚刚一样，如果我们用 表示 右边的所有子区间的和的最大值的话
，显然如果要让尽量大，一定会取 最大的那个，所以再维护一个数组 表示 之后sum的最大值即可。
但是这样的话你会发现由于区间的长度不固定了，我们在枚举左区间的时候是需要枚举两个端点的，复杂度又回到了，事实上这也不需要，我们其实只需要枚举左右区间的分界点，即用另外一个数组维护一个 左边所有子区间的最大值（这个过程和上述过程是对称的），然后分界点左右区间最大值相加即可。
另外，维护 右边的所有子区间的和的最大值还有一种办法，这是使用的动态规划的思想——用f[i]表示必须要选i的情况下i向右最大的区间和，，然后。

————————————————以下是变形二的思路——————————————

变形二：区间数目变多——找 个长度为 的不相交区间使得他们的权值和最大()
这个时候就必须要上动态规划了。
表示前 个数已经选了 个长度为 的不相交区间的最大权值和
你可能会得到这样一个转移方程： 即在前 个选了 j-1个区间的基础上选区间 这个长度为 的区间。
（如果你得的方程是的话，那么恭喜你，下面四段你都可以跳过了。）
这个的复杂度是的，显然很难令人满意。
我们可以先把以 结尾的长度为 的区间的和维护到一个数组 里面，，但是这似乎并没有在时间复杂度上有什么实质性的优化，但再认真观察这个转移方程你会发现实际上是一个前缀最大值。当 增加 1 的时候，对应的 也会增加1。
如果我们在算之前先把f数组的第 j-1 列全部算出来（这个是可以的，按行转移和按列转移都是可以的）并且在算第 j-1 列的f值的同时把对应的加进去，即维护一个数组来存，再维护出这个数组的前缀最大值，状态转移的时候就不需要枚举 了。算法时间复杂度变成了 ,问题得到解决。这是通过观察可以转移过来的区间有什么性质来优化掉转移过程中的枚举。
但是事实上真的需要这么麻烦么?仔细分析你会发现“在前 个选了 j-1 个区间的基础上选区间这个长度为 的区间”这个操作中，除了选以 为右边界的这个长度为 的区间的方案，其他的方案都是包含在中的，也就是说，枚举 完全是多余操作……其实说白了，每次转移我们只需要考虑第 数个选还是不选，要选它就要选它以前的 k-1 个数构成一个连续的 个数的区间；不选它，那扔掉就好。
这就告诉我们，推动态规划的时候要注意，要避免重复地枚举前一步的状态，对于有些题来说状态枚举重复了这个事情可能并不明显，但当你发现复杂度不行的时候，不要轻易否定它重启炉灶，多想一想，你其实有很多种方法来解决问题！

————————————————以下是变形三的思路——————————————

变形三：区间数目变多且不限制长度——找 个不相交且长度不限的区间使得他们权值和最大()
有了前一个题的经验，我们还是用表示前 个数里已经选了 个不相交区间的最大权值和，还是考虑第 个选不选。这个时候一个小问题出现了，如果我们要选 ，选中的区间数究竟是会+1呢还是不变呢？也就是说，我们不知道第 i-1 个数选没选所以没法转移……那怎么办？我们在状态的描述中强行规定 表示第 个数必须要选且前 个数里已经选了 个不相交区间的最大权值和，既然第 个数必须要选了，那么 即 可以接在上一个区间后面，或者成为一个区间的第一个元素。
还是刚刚那个问题，我们并不想要枚举 ，而这个式子含有 的部分也正好是f数组上一列的一个从1 开始的连续区间的最大值， 加 1 的时候 也相应加一，所以对上一列求一个前缀最大值即可。即我们在转移的时候维护一个数组表示 数组第 列前 个数的最大值，即所有的满足的的最大值 。所以, 这里有一个小技巧：当状态转移方程中等式右边包含一个区间的最值，且这个是区间一个端点固定另一个端点随着转移而递增的，就可以用前缀最值来维护，同样的情况，如果是求和，就用前缀和来维护。对于学有余力的同学，这个技巧还可以扩展：如果是一个等式右边是一个定长连续区间的最值，那么是可以用单调队列的来维护的。

————————————————看过大家题解之后的补充——————————————

@iamhpp 同学 关于变形三有更加简单而清晰的方法，我们来一起学习和分析一下：

设 表示前 个数，分成 段，第 个不选/选的最大值，转移方程：

就没有之前的需要求前缀最大值的问题了，为什么？

因为在上面的所有的 中 除了 ，其他的所有情况就是前 i-1 个数分成 段，第 i-1个不选的最大值，也就是的值，换句话说 ，这一部分其实就是上面的，就是上面那个前缀最大值的一部分。

实际上，这位同学的状态才是这个问题严谨而完整的状态，二维状态，表示第 个数必须选的情况下前 个数里已经选了 个的不相交区间的最大权值和时，实际上是将不选i的情况省略掉了，这种省略有的时候是可以省掉可算可不算的部分，但是在这个问题里，显然这种省略其实反而使得转移的时候麻烦了起来。

再次感谢@iamhpp 同学让我意识到了之前定义不完整状态是有可能出问题的。

但是各位同学，即使你定义的可能是个不完整的状态且导致出现了一些本可避免的麻烦，你其实还是有办法优化回去的，最后，优秀的算法们会殊途同归！

活动奖励：

在牛客博客中写出题解，并回复地址

审核通过可获得10-50牛币（依据题目难度和题解的内容而定）