记录编号	299103	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]数字序列	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.085 s
提交时间	2016-08-24 10:46:25	内存使用	2.69 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const long long INF=1000000000000000LL;
const int N=35010;
long long f[N],g[N],a[N],b[N];
long long st[N],fir[N],nxt[N],to[N];
long long s1[N],s2[N],top,cnt,n;
int main(){
	freopen("sequencec.in","r",stdin);
	freopen("sequencec.out","w",stdout);
	scanf("%lld",&n);b[0]=-1<<30;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i]-i;
	}b[++n]=1<<30;
	for(int i=1;i<=n;i++){
		int p=upper_bound(st+1,st+top+1,b[i])-st;
		if(p>top)top+=1;f[i]=p;st[p]=b[i];
	}
	for(int i=n;i>=0;i--){
		nxt[++cnt]=fir[f[i]];
		to[fir[f[i]]=cnt]=i;
	}
	for(int i=1;i<=n;i++)g[i]=INF;
	for(int x=1;x<=n;x++)
		for(int i=fir[f[x]-1];i;i=nxt[i]){
			int p=to[i];
			if(p>x)break;
			if(b[p]>b[x])continue;
			for(int j=p;j<=x;j++)
				s1[j]=abs(b[p]-b[j]),s2[j]=abs(b[x]-b[j]);
			for(int j=p+1;j<=x;j++)
				s1[j]+=s1[j-1],s2[j]+=s2[j-1];
			for(int j=p;j<x;j++)
				g[x]=min(g[x],g[p]+s1[j]-s1[p]+s2[x]-s2[j]);	
		}
	printf("%lld\n%lld\n",n-top,g[n]);
	return 0;
}