P3195
求出玩具的前缀和 \(S\)。
设 \(f_i\) 表示区间 \([1,i]\) 的最大答案。开始应该是 \(f_0=0\)。
\(f_i =\max_{1 \le j < i}f_j+(i+S_i-L-1-(j+S_j))^2\)。
\(f_i =\max_{1 \le j < i}f_j+(i+S_i-L-1)^2+(j+S_j)^2-2(i+S_i-L-1)(j+S_j)\)。
设 \(g_i=i+S_i,k=L+1\)，那么 \(f_i=\max_{1 \le j<i}f_j+(g_i-k)^2+g_j^2-2g_j(g_i-k)\)。
把 \(i\) 这边的去掉，就是 \(f_i=(g_i-k)^2+\max_{1 \le j<i} f_j+g_j^2-2g_jg_i-2g_jk\)。
考察两个点 \(j_1<j_2\)，且 \(j_1\) 不劣于 \(j_2\) 的条件。
那就是 \(f_{j_1}+g_{j_1}^2-2g_{j_1}(g_i-k) \le f_{j_2}+g_{j_2}^2-2g_{j_2}(g_i-k)\)
\[f_{j_1}-f_{j_2}+g_{j_1}^2-g_{j_2}^2-2g_{j_1}(g_i-k)+2g_{j_2}(g_i-k) \le 0 \]\[f_{j_1}-f_{j_2}+g_{j_1}^2-g_{j_2}^2-2g_{j_1}(g_i-k)+2g_{j_2}(g_i-k) \le 0 \]\[f_{j_1}-f_{j_2}+g_{j_1}^2-g_{j_2}^2\le(2g_{j_1}-2g_{j_2})(g_i-k) \]记 \(F(j)=f_j+g_j^2\)，那么 \(F(j_1)-F(j_2) \le (g_{j_1}-g_{j_2})2(g_i-k)\)
由于 \(j_1 <j_2\)，所以 \(g_{j_1}<g_{j_2}\)，那么 \(\frac{F(j_1)-F(j_2)}{g_{j_1}-g_{j_2}} \ge 2(g_i-k)\)。
换言之，\(\frac{F(j_2)-F(j_1)}{g_{j_2}-g_{j_1}} \ge 2(g_i-k)\)。
记 \(slope(i,j)=\frac{F(j)-F(i)}{g_j-g_i}\)，其中 \(i<j\)。
然后，套路的考虑三个点 \(l<mid<r\)，\(mid\) 为最优决策的条件。
需要满足 \(slope(l,mid)\le 2(g_i-k)，slope(mid,r) \ge 2(g_i-k)\)。
那么 \(slope(l,mid) \le slope(mid,r)\)。
如果不是这样，\(mid\) 就一定不是最优决策，删掉即可。最后剩下一个下凸壳。
然后在 \(i\) 操作的时候，只需要找到第一个斜率超过 \(2(g_i-k)\) 的点即可。
AT_dp_z Frog 3
\(f_i=h_i^2+C+\min_{1 \le j<i} f_j+h_j^2 -2h_ih_j\)
对后面进行优化。
假设 $j_1 $ 不比 \(j_2\) 劣，且 \(j_1<j_2\)。
那就是 \(f_{j_1}+h_{j_1}^2-2h_ih_{j_1} \le f_{j_{2}}+h_{j_2}^2 -2h_ih_{j_2}\)。
移项，容易得到 \(2h_i(h_{j_2}-h_{j_1})\le f_{j_2}-f_{j_1}+h_{j_2}^2-h_{j_1}^2\)。
记 \(F(j)=f_{j}+h_j^{2}\)。
原式可化为 \(2h_i \le \frac{F(j_2)-F(j_1)}{h_{j_2}-h_{j_1}}\)。
记 \(slope(i,j)=\frac{F(j)-F(i)}{h_{j}-h_{i}}(i<j)\)
假设有三个决策 \(l,mid,r\)，其中 \(l<mid<r\)。若 \(mid\) 为最优决策点，需要满足的条件是：
$slope(l,mid) \le 2h_i,solpe(mid,r) \ge 2h_i $
那么 \(solpe(l,mid) \le solpe(mid,r)\)。
那么如果有一对 \(l<mid<r\)，满足 \(solpe(l,mid) \ge solpe(mid,r)\)，那么 \(mid\) 一定不可能成为最优决策，可以删掉。
那么最后剩下的相邻两个点一定不会出现斜率 $\ge $ 的情况，那么斜率就是单调递增的一个下凸壳。
那么斜率单调递增了，对于一对斜率不超过 \(2h_i\) 的节点 \((j_1,j_2),j_1 <j_2\)，那么 \(j_2\) 一定比 \(j_1\) 优，那么应该选的是靠后的，但是对于超过了的，那 \(j_1\) 就不比 \(j_2\) 劣，直接无敌。
因为 \(h\) 单调，所以不会出现之前不优后来优的情况。
至于等号，有一个技巧就是全都带上肯定是没问题的。
标签：slope,le,2h,mid,笔记,斜率,2g,动态,规划 From： https://www.cnblogs.com/aCssen/p/18340015