XXVIII.[HAOI2006]数字序列
第一问：
正难则反。我们考虑从这个序列中找出最多可以保留的数。
如果两个下标\(i,j(i<j)\)都是要保留的，那么保留的充要条件就是
\(a_j-a_i\geq j-i\)
因为\((i,j)\)开区间中的其它数要保证仍然有可以修改到的位置。例如 10 4 3 12 这组数据中，10和12便不能同时选择，因为4和3要有修改的位置。
上面式子调换一下，便是
\(a_j-j\geq a_i-i\)
设\(a_i-i=b_i\)，则
\(b_j\geq b_i\)便是充要条件。
当我们找出了完整的\(b\)数组后，发现\(b\)中的最长不降子序列便是可以保留的位置。
然后第一问答案就是\(n-\text{b中LIS的长度}\)。
第二问：
实际上就是让\(b\)中LIS的长度为\(n\)。
考虑在第一问中找出的一条LIS上修改（注意LIS很有可能不止一条）。
我们在LIS中找出相邻的两个下标\(j,i(j<i)\)
则一组合法的修改结果肯定是一个“台阶”形。
我们发现，对于一段“台阶”：
如果它向下的箭头比向上的箭头要多，那么台阶上移一定不会更劣。反之亦然。
比如上图最左端那级台阶，就是上移下移都可以；中间的台阶，向上移更优；右面的台阶，向下移最好。
这样我们就可以构思出一种移台阶的方法：
对于一段台阶，如果它向上最好，则一直向上移直到和右边的下一段台阶齐平。然后合并两段台阶，再对新生成的这段台阶进行类似的操作。这种操作一定不会使答案变差。
则全部移完后，我们发现原本一小段一小段的台阶，要么同左边合并了，要么同右边合并了，反正最后一定是左边与左端点有一段台阶，右边与右端点有一段台阶。我们可以枚举左右台阶间的断点取\(\min\)。
这样我们就可以DP了。设\(f_i\)表示以\(i\)结尾的LIS的长度，\(g_i\)表示将\([1,i]\)中所有台阶全都移完，且\(i\)是某条LIS中的一个位置时的最小代价。显然，\(g_i\)能从所有\(j<i,b_j<b_i,f_j=f_i-1\)的\(j\)转移过来。如果令\(b_0=-\infty,b_{n+1}=+\infty,f_0=0,f_{n+1}=\max\limits_{i=1}^{n}\{f_i\}+1\)的话，则答案为\(g_{n+1}\)。
在极端数据下，这种暴力转移复杂度是\(O(n^3)\)的（枚举\(i\)是\(O(n)\)的，枚举\(j\)在极端数据下是\(O(n)\)的，枚举断点也是\(O(n)\)的）。但是，“数据随机”让这个算法的期望复杂度优化成了\(O(n\log^2n)\)，轻松通过。
代码：
#include<bits/stdc++.h>
using namespace std;
const int INF=1e6;
int n,a[50100],b[50100],f[50100],t[50100],lim,mx,g[50100],pre[50100],suf[50100];
vector<int>v;
void add(int x,int val){
while(x<=lim)t[x]=max(t[x],val),x+=x&-x;
}
int ask(int x){
int qwq=0;
while(x)qwq=max(qwq,t[x]),x-=x&-x;
return qwq;
}
vector<int>q[50100];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)b[i]=a[i]-i,v.push_back(b[i]);
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size();
for(int i=1;i<=n;i++)b[i]=lower_bound(v.begin(),v.end(),b[i])-v.begin()+1;
for(int i=1;i<=n;i++)f[i]=ask(b[i])+1,add(b[i],f[i]),mx=max(mx,f[i]);
for(int i=1;i<=n;i++)b[i]=a[i]-i;
printf("%d\n",n-mx);
q[0].push_back(0);
memset(g,0x3f3f3f3f,sizeof(g));
b[0]=-INF;
b[n+1]=INF;
g[0]=0;
f[n+1]=mx+1;
for(int i=1;i<=n+1;i++){
q[f[i]].push_back(i);
for(auto j:q[f[i]-1]){
if(b[j]>b[i])continue;
// printf("%d %d:\n",j,i);
pre[j]=suf[i]=0;
for(int k=j+1;k<i;k++)pre[k]=pre[k-1]+abs(b[k]-b[j]);
for(int k=i-1;k>j;k--)suf[k]=suf[k+1]+abs(b[k]-b[i]);
// for(int k=j;k<i;k++)printf("%d ",pre[k]);puts("");
// for(int k=j+1;k<=i;k++)printf("%d ",suf[k]);puts("");
for(int k=j;k<i;k++)g[i]=min(g[i],g[j]+pre[k]+suf[k+1]);
}
}
// for(int i=0;i<=n+1;i++)printf("%9d ",f[i]);puts("");
// for(int i=0;i<=n+1;i++)printf("%9d ",b[i]);puts("");
// for(int i=0;i<=n+1;i++)printf("%9d ",g[i]);puts("");
printf("%d\n",g[n+1]);
return 0;
}