BZOj1049 [HAOI2006]数字序列

题面

​ 现在我们有一个长度为n的整数序列A。但是它太不好看了,于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。

题解

第一问:

​ 设$b[i] = a[i] - i$那么变成了修改最少的b,使得b非单调递减,也就是对于每一个$b[i+1] >= b[i]$

​ 再转化一下,就是使得不修改的b最多,那么哪些不修改呢?显然是b的LIS呀。

​ 然后转化成经典算法。

第二问:

​ ………………………………………………不会

​ 于是:szOhttp://hzwer.com/5325.html

​ szOhttp://pan.baidu.com/share/link?uk=2651016602&shareid=1490516411

​ 大概就是设$f[i]$表示1到i的答案,$f[i]$向$f[j]$转移,然后一个结论是一定有一个分割点,使得左边一半是属于$b[i]$,右边一半属于$b[j]$

​ 然后这样理论上是$O(n^3)$但是数据随机可以过。

​ 然后优化是考虑先全部变成$b[j]$,然后类似的求一个前缀min,预处理出来。

https://www.cnblogs.com/czllgzmzl/p/5186419.html

文章目录
  1. 1. 题面
  2. 2. 题解