CF573E 题解

· · 题解

提供一种不开 O2 不使用快读快写总用时 1.47s 的代码的思路。

朴素策略

有一个 O(n^2) 的较为简单的 dp 。

设 dp_{i,j} 表示前 i 个数选 j 个数组成子序列的最大答案，此时有

dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-1}+a_i\times j)

优化猜想

$$\forall j< k_i,\ dp_{i,j}=dp_{i-1,j}$$ $$\forall j\ge k_i,\ dp_{i,j}=dp_{i-1,j-1}+j\times a_i$$ 证明 --- 考虑对于 $dp_i$ 构造一个**差分序列** $f_i$。若猜想成立，由上述 $k_i$ 的定义，有 $dp_{i-1,k_i-1}\ge dp_{i-1,k_i-2}+a_i\times (k_i-1)$ 且 $dp_{i-1,k_i}< dp_{i-1,k_i-1}+a_i\times (k_i-1)$，对应 $\frac{f_{i-1,k_i-1}}{k_i-1}\ge a_i$ 且 $\frac{f_{i-1,k_i}}{k_i}<a_i$。 **注意 $a_i$ 取值与 $f_{i-1}$ 无关，所以 $\frac{f_{i-1,j}}{j}$ 关于 $j$ 单调不增**。 计算 $dp_i$ 值后，可知 $$\forall j<k_i,f_{i,j}=f_{i-1,j}$$ $$\forall j>k_i,f_{i,j}=f_{i-1,j-1}+a_i$$ $$f_{i,k_i}=a_i\times k_i$$ 简单来讲，计算 $dp_i$ 后，$f_i$ 等效于在 $f_{i-1}$ 中，对 $f_{i-1,k_i-1}$ 后整体加上 $a_i$，然后在 $f_{i-1,k_i-1}$ 后插入 $a_i\times k_i$。 考虑证明**若猜想成立，则 $\frac{f_{i,j}}{j}$ 关于 $j$ 仍单调不增**。 对于 $\forall j<k_i$，显然 $f_{i,j}$ 不发生变化。 对于 $k_i$，由于 $\forall j<k_i,\frac{f_{i-1,j}}{j}<a_i$ 且 $\frac{f_{i-1,k_i}}{k_i}=\frac{k_i\times a_i}{k_i}=a_i$，单调性显然也没有改变。 对于 $\forall j>k_i$，有 $\frac{f_{i-1,j}}{j}\ge \frac{f_{i-1,j+1}}{j+1}$，故而 ${f_{i-1,j}}\ge \frac{j}{j+1}\times f_{i-1,j+1}$。 同时 $f_{i,j+1}=f_{i-1,j}+a_i,f_{i,j+2}=f_{i-1,j+1}+a_i$，考虑从结论**倒推**，可得 $$\begin{aligned}\frac{f_{i,j+1}}{j+1}&>\frac{f_{i,j+2}}{j+2}\\ \frac{f_{i-1,j}+a_i}{j+1}&>\frac{f_{i-1,j+1}+a_i}{j+2}\\ f_{i-1,j}+a_i&>\frac{j+1}{j+2}\times (f_{i-1,j+1}+a_i)\\ f_{i-1,j}+a_i&>\frac{j+1}{j+2}\times f_{i-1,j+1}+\frac{j+1}{j+2}\times a_i\\ f_{i-1,j}&>\frac{j+1}{j+2}\times f_{i-1,j+1}-\frac1{j+2}\times a_i\end{aligned}$$ 而 $$\begin{aligned}&\phantom{\,=\,}\left(\frac{j}{j+1}\times f_{i-1,j+1}\right)-\left(\frac{j+1}{j+2}\times f_{i-1,j+1}-\frac{1}{j+2}\times a_i\right)\\&=\frac{((j+2)\times j-(j+1)\times (j+1))\times f_{i-1,j+1}+(j+1)\times a_i}{(j+1)(j+2)}\\&=\frac{(j+1)\times a_i-f_{i-1,j+1}}{(j+1)(j+2)}\ge 0\end{aligned}$$ 最后由 $f_{i-1}$ 单调不增一定有 $f_i$ 单调不增。而 $f_1$ 只有一个数（单调不增），**通过数学归纳法可得所有 $f_i$ 均是单调不增，从而证明猜想成立。** 实现 --- 这里我使用的是 FHQ Treap 实现二分求 $k_i$，单点插入，区间加。具体来讲，**只维护 $f$ 数组**，在 FHQ Treap 的按权值分裂时，按 $f_{i,j}$ 与 $a_i\times j$ 的大小关系为二分依据。时间复杂度为 $O(n\log n)$。 核心代码 --- ```cpp void vSplit(int p,int rnk,int &x,int &y){ if(!p){ x=y=0; return; } Pushdown(p); if(a*(rnk+siz(ls(p))+1)>val(p)){ y=p;//y树内会是 f[i-1][k[i]]~f[i-1][i-1] vSplit(ls(p),rnk,x,ls(p)); } else{ x=p;//x树内会是 f[i-1][1]~f[i-1][k[i]-1] vSplit(rs(p),rnk+siz(ls(p))+1,rs(p),y); } Pushup(p); } ``` p.s. 感谢 [plate_let](https://www.luogu.com.cn/user/177524) 巨佬提供的思路！