leetcode 周赛 505,54名

零、背景

这次比赛最后一题比较难，涉及到WQS二分算法（又名Alien Trick 或 拉格朗日松弛），触发我的知识盲区了。
网上找了模版，现场调试，最终也没调试通过，遗憾。

本场题型概览如下。
A 题：枚举。
B 题：二进制枚举。
C 题：二维DP+单调队列或线段树优化。
D 题：一维DP+WQS二分优化。

一、区间内的兼容数字之和 I

题意：问数字 n 左右距离 k 之内的数字，哪些数字与 n 的与运算结果为0。
求所有满足条件数字的和。
数据范围：k 小于 100

思路：枚举

k 不大于 100，枚举左右 200 个数字，判断哪些满足要求即可。

二、成本限制的有效二进制字符串

题意：给一个数字 n 和 k，求长度为 n 的二进制满足 1 的个数不超过 k 且不存在连续的 1。
数据范围：n 不大于 12

思路：二进制枚举

n 不大于 12，二进制个数不超过 2^12 个，dfs 枚举所有合法的二进制即可。

三、非重叠子数组最大和 I

题意：给一个数组，至多选择 m 个不重叠的子数组，且子数组长度在 [l,r] 之间，问选择子数组的最大总和是多少。
数据范围：n 不大于 1000

思路：二维DP+单调队列优化

很容易写出一个状态转移方程。

状态：f(i,k) 前 i 个元素至多选择 k 个子数组的最大和。

状态转移方程:

  f(i,k)
= max(f(j, k-1) + pre(i) - pre(j))
= max(f(j, k-1) - pre(j)) + pre(i)
l < i - j < r

观察状态转移方程，max 的值与 i 无关，只与每个位置自身有关系，然后求区间最大值。

最简单的方法是使用线段树，直接求区间最值即可。
复杂度：O(n^2 log(n))

随着 i 的增大，考虑到这个区间也在向右增大，故可以使用滑动窗口来做这道题。
显然，窗口内，如果左边的值比右边的小，则左边的值显然不可能是最优答案。
故只需要维护一个单调递减的滑动窗口即可。
复杂度：O(n^2)

四、非重叠子数组最大和 II

题意：给一个数组，至多选择 m 个不重叠的子数组，且子数组长度在 [l,r] 之间，问选择子数组的最大总和是多少。
数据范围：n 不大于 10^5

思路：WQS二分算法、Alien Trick、拉格朗日松弛

题目与第三题一模一样，只是数据范围变大了。

由于数据范围太大，状态转移方程必须去掉 m 才行。

如果去掉限制 m，类似于 01背包转化为完全背包，可以重复选择了。

状态：f(i) 前 i 个元素选择任意子数组的最大和以及个数。

状态转移方程:

  f(i)
= max(f(j) + pre(i) - pre(j))
= max(f(j) - pre(j)) + pre(i)
l < i - j < r

此时复杂度降低为 O(n)
状态转移方程顺便记录选择的个数，假设为 M。

如果在不加个数限制的情况下，假设最优答案为 M。

如果 M 等于 0，则说明答案为负数，此时无奈只能选择 1 个了。
直接使用类似于 01 背包，只选一个的 O(n) 算法来求最优值。

如果 M 不大于 m，则显然这个就是答案。

如果 M 大于 m，则说明数组中穿插着很多大负数，通过拆分更多的小数组，规避掉大负数，从而得到更大的和。
这个也说明，M 从 1 到 M 之间，拆分的数组越多，答案越大，在之后就答案越小，这显然是一个上凸函数，且 M 是最值分割点。

上凸函数的斜率是递减的，故我们可以构造一个新的函数。

F(i) = f(i) - M*λ

其中 M 为 F(i) 最优值选择的子分组个数， λ 是斜率。

如下图，确定 λ 后，就可以自动贪心求出最优的 M。
而且 λ 与 M 是成正比的，即存在单调性。

因此，可以二分 λ，找到 M=m 时的 λ。

F(i) 求出来了，M*λ 也有了，f(i)就也算出来了。

复杂度：O(n log(n))

这个算法国内称为 WQS二分算法，国外称为 Alien Trick，理论知识是拉格朗日松弛。
关于怎么证明新函数的最优值就是旧函数的最优值，证明方法比较复杂，这里就不介绍了。

五、最后

这次比赛最后一题比较难，属于 IOI 难度的了，后面有机会再深入研究下这个算法。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code