SCOI2020模拟3-B 加减

首先我们注意到一个规律(这辈子都注意不到的),样例输出按照奇数位置和偶数位置分成两排,然后这两排的值是凸的。所以有个结论:所有选奇数个最佳答案的函数是凸的,偶数同理。

然后我们考虑分治,分成左边和右边单独处理。然后我们需要维护四个凸函数,因为有两个信息任意组合(开头位置的奇偶/取出个数的奇偶)每个凸函数就是代表这个区间内,开头位置奇偶性为ii,取的个数奇偶为jj的最大价值。之所以需要维护开头位置的奇偶是为了维护负值(奇数位置为负),最后的答案开头位置是偶数(开头为0)。

然后我们考虑如何合并左右的答案。我们发现这是个闵可夫斯基和,其实就是MAXMAX和卷积。就是ansi=maxj+k=i(gj+fk)ans_i=max_{j+k=i}{(g_j+f_k)}。这里有一些参考资料: 闵可夫斯基和 闵可夫斯基和-维基百科

然后这个东西可以贪心的合并。因为两边要合并的函数都是凸的,所以我们用双指针每次选取差分(后面减前面)最大的即可科技为了我(第一位是0)。然后就没了QAQ