P5308 凸性口胡证明

· · 个人记录

两节晚自习抛弃常规作业的成果(?

l1nk
record

最多轮次数为 n 轮
此时答案为

\sum_{i=1}^n\frac{1}{n-i+1}=\sum_{i=1}^ni^{-1}

而最少轮次为 1 轮
此时答案

1=\sum_{i=1}^nn^{-1}

这时候其实已经可以猜测凸性了

再多推几步：
我们考虑把某个 \large\frac{φ+ζ}{n-a} 拆成 \large\frac{φ}{n-a}+\frac{ζ}{n-a-φ}
因为有

\frac{ζ}{n-a} \lt \frac{ζ}{n-a-φ}

所以答案增加了

\frac{ζφ}{(n-a)(n-a-φ)} \le \frac{φ}{φ+1}ζ

而我们选的 φ 和 ζ 都满足 \ge1 ，所以每次将轮数增加时都会使答案增加

设 k=n-a ，则

Δ(φ)=\frac{ζφ}{k^2-kφ}

因为 ζ 很讨厌而 ζ+φ \le k
所以

Δ(φ)\le \frac{(k-φ)φ}{k(k-φ)}=\frac{φ}{k}

那么因为决策的最优选择，我们首先使用的应该是最优的 φ
也就是说对于同一个 k ，随着决策次数增加， Δ(φ) 逐渐减小
而我们又将从最优 k 选起 尽量使这个值最大
所以每次决策后 Δ(φ,k) 不会再增大

所以是一个上凸壳， \text{Q.E.D.}

把本子上记的斜优过程记下来：

设 f_i 为淘汰了 i 个人的最多奖金
（这样设会出现一个 max_{j \lt i} ，这种形式斜优更熟悉）

f_i=max_{j=1}^{i-1}\{f_j+\frac{i-j}{n-j}\}

然后感觉就很能斜优

如果 j 优于 k :

f_j+\frac{i-j}{n-j} \ge f_k+\frac{i-k}{n-k}

也就是

(f_j-\frac{j}{n-j})-(f_k-\frac{k}{n-k}) \ge (\frac{1}{n-k}-\frac{1}{n-j})i

右边有个反向怪，提出来一个 -1

\frac{H_j-H_k}{B_j-B_k} \ge -i

其中

H_x=f_x-\frac{x}{n-x}\,,\,B_x=\frac{1}{n-x}

但是有个 \ge 号，很难看
所以两边乘上 -1

\frac{H'_j-H'_k}{B_j-B_k} \le i

其中

H'_x=-H_x

然后右边单增，分母单增
直接单调队列维护凸壳即可