※ 引述《FRAXIS (喔喔)》之铭言： : 题目：给定一含有 n 个整数的阵列 A ，找出不相交的 k 个子阵列其总和最大。 : 也就是要找 k 组索引对 (b1, e1), ... (bk, ek), bi < ei 且 ei < b_{i+1} : 使得 A[bi...ei] 的总和最大。 最近有人跟我说这一题有另一种想法，所以跟大家分享一下。 可以参考这个网站： http://www.serbanology.com/article/The%20Trick%20From%20Aliens 解题的技巧叫做 Alien's Trick (IOI 2016 的 Aliens 题）或是 WQS binary search。 简单来说，如果 A 是给定，我们令 f(x) 为 不相交 x 个子阵列最大的总和 （此时 x 是变量，虽然我们只想算 f(k)）。 然後引入 Lagrange multiplier λ，计算 L(x, λ) = f(x) - λx。 可以想像 λ 是建立一个新子阵列的 penalty 。 （我其实看不太出来这跟 Lagrange multiplier 有甚麽关系，虽然函数很像，但是 Lagrange multiplier 主要是在处理连续的函数而不是离散函数） 此时我们会发现 λ 增加时，argmin_x L(x, λ) 会减少。 当 λ 是 0 时，因为建立子阵列的 penalty = 0，就是挑 A 中所有的正数，每一个正数 是一个独立的子阵列。 当 λ 很大时，就会挑比较少子阵列。 想法就是 binary search λ，直到 argmin_x L(x, λ) = k 为止， 而 argmin_x L(x, λ) 可以用 DP 在线性时间内算出。 λ 一般都可以找出合理的上限 U，所以不会时间复杂度可以是 O(n lg U)。 （真要分析的话，只需要考虑 λ = A[i..j] 总和的情况， 因为 i, j 只有 O(n^2) 组合，而且可以藉由建构 prefix sum array 的方式计算 子阵列总和，所以应该 O(n lg n) 算法是可行的） --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 73.202.90.47 (美国) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1613627212.A.145.html