P3202 [HNOI2009] 通往城堡之路-526互联

考虑将每个支撑点都先设成其下限高度，即 \(h_i\gets h_1-(i-1)\times d\)，这样就只会提高某些支撑点的高度。

显然每次提高的是一个后缀。提高某个后缀的贡献是当前高度低于原先高度的支撑点数量减去当前高度不低于原先高度的支撑点数量。选择贡献最大的后缀直到最后一个支撑点的高度等于原先高度为止。注意起点不能动，相邻两个支撑点的高度差在提高某个后缀时不能超过 \(d\)。

因为前面提不提高对于后面没有影响，所以正确性显然。