洛谷 P2501 [HAOI2006]数字序列

第一问

实质是最大化不修改的数。

假设 \(i,j\) 不修改（\(j<i\)），那么必须满足 \(a_i-a_j\geq i-j\)。

移项：\(a_i-i\geq a_j-j\)。

设 \(b_i=a_i-i\)。

求 \(b\) 的最长不下降子序列即可。设 \(f_i\) 为求这个的 dp 值。

第二问

实质上是要求使得 \(b\) 单调不降。

继续 dp，设 \(g_i\) 表示前 \(i\) 个的答案。

那么 \(g_i=g_j+w(j,i)\)。

注意 \(j\) 必须满足 \(f_j+1=f_i\)。

结论：操作后的序列 \([j,i]\)，一定前面一部分（可能没有）为 \(b_j\)，后面一部分为 \(b_i\)。

证明：不会，感性理解。

所以枚举分界点，前后算一算即可。

因为数据随机，所以能过。