CF1442D Sum

WeLikeStudying · 2021-12-11 10:26:48 · 题解

• 本来不敢发题解，只用作自己记录下（主要是作者太菜了）。
• 但作者一不小心点了一下题解键（在还没有打完的情况下），所以不得不去写啦。
• 请把我的题解置于那些大佬的下方。

题意

• 原题题面。
• 给定 n 个非负数组，每个数组的元素可以被取当且仅当该数组内小于该元素的数都被取了。
• 在这 n 个数组中取 k 个数，要求取的数和最大。

思路

• 传统的动态规划是 O(nk^2) 的。
• 似乎也没啥可以优化的。
• 暴力实现，作者暴力写挂就离谱，下次用滚动数组一定要注意初始化问题，作者还忘记开长整型了 QWQ。
• 所以我们尝试发现性质：锁定非负和数组元素分别非降的性质。
• 你会发现对于两个没有选完的数组，比较它们的最后一个元素大小，然后贪心地抛弃更小的前面的选取更大的后面的总是没错的。
• 也就是说，存在一种最优选取方案满足只有一个数组只选了一部分（与之对应的是不选或选完）。
• 理想很美好，那么难道是枚举没选完的数组然后再跑背包？O(n^2k)（那不就白发现性质了吗）。
• 我们转入实际实现。

分块做法

• 设块长为 x，块数为 \dfrac nx。
• 对除开每块的全放进行预处理：\Theta(\frac nx \cdot nk)=\Theta(\frac {n^2k}x)。
• 块内枚举物品对让其他物品更新 \Theta(\frac nx\cdot x\cdot xk)=\Theta(nkx) 。
• 总复杂度为 \Theta(\frac {n^2k}x+nkx) 取 x=\sqrt n 得到 \Theta(n\sqrt nk) 的复杂度，应该可过。
• 代码实现。
• 作者在判断语句上犯了玄学错误（看错变量名！！）我靠，以后提交前一定要看一遍程序！！

分治做法

• 学分治也就图一乐。
• 作者想了想发现很妙啊，而且放在分块后面很合适。
• 我们本质上就是要求出除开每个数的 01 背包。
• 之前的分块做法相当于先求出来除开每个块的 01 背包，然后再求出除开每个数的 01 背包，那么如果你把块分得更细呢？
• 这就是分治做法：
• 对于一个区间，如果我们已经算出除开该区间的背包，那么我们可以 \Theta(nk) 更新除开左区间的背包（加右区间的数），同理更新左区间的背包。
• 可以列出递推式 T(n)=2T(n/2)+nk，它的解是 \Theta(nk\lg n)，这也是分治做法的时间复杂度。
• 具体实现可能较分块复杂，而且必须开 k\lg n 的空间（不过对于题目条件来说这算不了啥），但可以用类似栈的方法实现。
• 作者忘记弹栈属实离谱。
• 代码实现。
• 比分块好打属实离谱。