Description
现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。
Input
第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。
Output
第一行一个整数表示最少需要改变多少个数。 第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。
Sample Input
4
5 2 3 5
5 2 3 5
Sample Output
1
4
4
HINT
【数据范围】
90%的数据n<=6000。
100%的数据n<=35000。
保证所有数列是随机的。
题解
之前忘写上来了。第一问很简单，不讲了。
对于第二问，我们大概可以猜到，不在子序列中的数只要改到跟某个数相同即可。所以我们要找的每对f[i]和f[i-1]。因为数据是随机的，所以可以认为两者之间距离很小，只要枚举中间的端点即可。
注意：因为在枚举f[i]中，第i个数是保证不改的，所以第n个数不管怎样都不会被改。这显然是错的，所以我们要在第一问前就在序列尾加一个无穷大的元素。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int n,a[35002],f[35002],s[35002],top;
int last[35002],zz;
struct lian{int to,pre;} e[35002];
ll g[35002],sm[35002],sum[35002];
void init()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
{scanf("%d",&a[i]);
a[i]-=i;
}
}
int erf(int x)
{
int l=0,r=top,mid,p;
while(l<=r)
{mid=(l+r)>>1;
if(s[mid]<=a[x]) {p=mid; l=mid+1;}
else r=mid-1;
}
return p;
}
void dp()
{
int i,j,p,ans=1;
a[++n]=1<<30; f[1]=1;
memset(s,127,sizeof(s));
top=1; s[1]=a[1]; s[0]=0-1<<30;
for(i=2;i<=n;i++)
{p=erf(i);
f[i]=p+1; s[p+1]=min(s[p+1],a[i]); top=max(p+1,top);
ans=max(ans,f[i]);
}
//for(i=1;i<=n;i++) printf("%d\n",f[i]);
//printf("\n");
printf("%d\n",n-ans);
}
void insert(int x,int y)
{
zz++; e[zz].to=y; e[zz].pre=last[x]; last[x]=zz;
}
void find()
{
int i,j,k,p;
for(i=n;i>=0;i--)
{g[i]=1<<30; insert(f[i],i);}
g[0]=0; a[0]=0-(1<<30);
for(i=1;i<=n;i++)
for(j=last[f[i]-1];j;j=e[j].pre)
{p=e[j].to;
if(p>i) break;
if(a[p]>a[i]) continue;
for(k=p;k<=i;k++)
{sm[k]=abs(a[p]-a[k]); sum[k]=abs(a[i]-a[k]);}
for(k=p+1;k<=i;k++)
{sm[k]+=sm[k-1]; sum[k]+=sum[k-1];}
for(k=p;k<i;k++)
g[i]=min(g[i],g[p]+sm[k]-sm[p]+sum[i]-sum[k]);
}
//for(i=1;i<=n;i++) printf("%d\n",g[i]);
printf("%lld\n",g[n]);
}
int main()
{
//freopen("sequence.in","r",stdin);
//freopen("sequence.out","w",stdout);
init(); dp(); find();
return 0;
}