题解 CF573E 【Bear and Bowling】

有一种神奇的O(n)贪心做法，在CF上能过，然鹅是错的，随便卡卡就WA了。

以下算法比标算的O(n\sqrt n\log n)要优，证明来自YuHaoxiang。

有一个O(n^2)的dp：设f_{i,j}表示前i个数选j个数的最大值。

有一个结论：对于a_i，一定存在一个1\leqslant k\leqslant i使得任意0\leqslant j < k，有f_{i,j}=f_{i-1,j}；任意k\leqslant j\leqslant i，有f_{i,j}=f_{i-1,j-1}+j\times a_i。

即存在一个分界点，使得左边的都不取a_i，右边的都取了a_i。

下面来证明这个结论。

当i=0,1时显然成立。

设F_{i,j}表示前i个数选j个数，最大方案选的下标集合，V(F_{i,j})表示取这个下标集合的值。

假设存在一个j，使得i\in F_{i,j}且i\notin F_{i,j+1}。

设F_{i-1,j}=F_{i-1,j-1}\cup\{x\}，F_{i-1,j+1}=F_{i-1,j}\cup\{z\}=F_{i-1,j-1}\cup\{x,z\}，F_{i,j}=F_{i-1,j-1}\cup\{i\}。

由假设得F_{i,j+1}=F_{i-1,j+1}=F_{i-1,j}\cup\{z\}。

令每种方案的值各不相同（相同可以通过扰动来避免），则f_{i-1,j}< f_{i,j}。

由此可得V(F_{i-1,j-1}\cup\{z\})< V(F_{i-1,j-1}\cup\{x\})。

1. 若x<z，则V(F_{i-1,j-1}\cup\{z\})< V(F_{i-1,j-1}\cup\{x\})< V(F_{i-1,j-1}\cup\{i\})。由于x<z且x<i，所以V(F_{i-1,j-1}\cup\{x,z\})<V(F_{i-1,j-1}\cup\{x,i\})。
2. 若x>z，则V(F_{i-1,j-1}\cup\{x\}))< V(F_{i-1,j-1}\cup\{i\})。由于z<x且z<i，所以V(F_{i-1,j-1}\cup\{z,x\})< V(F_{i-1,j-1}\cup\{z,i\})。又有V(F_{i-1,j-1}\cup\{z\})< V(F_{i-1,j-1}\cup\{x\})，由于z< i且x< i，所以V(F_{i-1,j-1}\cup\{z,i\})< V(F_{i-1,j-1}\cup\{x,i\})。所以V(F_{i-1,j-1}\cup\{z,x\})< V(F_{i-1,j-1}\cup\{x,i\})。

综上，V(F_{i-1,j-1}\cup\{z,x\})< V(F_{i-1,j-1}\cup\{x,i\})。

所以f_{i-1,j+1}< f_{i-1,j}+(j+1)\times a_i，即i\in F_{i,j+1}，与假设矛盾。

由数学归纳法可知结论成立。