本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

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

　　第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。n<=35000,保证所有数列是随机的

　　第一行一个整数表示最少需要改变多少个数。 第二行一个整数，表示在改变的数最少的情况下，每个数改变
的绝对值之和的最小值。

 1 //It is made by ljh2000
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <string>
10 using namespace std;
11 typedef long long LL;
12 const int MAXN = 35011;
13 const LL inf = (1LL<<50);
14 int n;
15 LL a[MAXN],g[MAXN],cost1[MAXN],cost2[MAXN],b[MAXN],c[MAXN],ans,f[MAXN];
16 vector<int>w[MAXN];
17 inline int getint(){
18     int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
19     if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
20 }
21 inline int find(LL x){ int l=1,r=n,pos=0,mid; while(l<=r) { mid=(l+r)>>1; if(c[mid]<=x) l=mid+1,pos=mid; else r=mid-1; } return pos; }
22 inline void work(){
23     n=getint(); for(int i=1;i<=n;i++) a[i]=getint(),b[i]=a[i]-i; a[++n]=inf; b[n]=a[n]-n; for(int i=1;i<=n;i++) c[i]=g[i]=inf;
24     for(int i=1;i<=n;i++) f[i]=find(b[i])+1,c[f[i]]=min(c[f[i]],b[i]); for(int i=1;i<=n;i++) ans=max(ans,f[i]);
25     printf("%lld\n",n-ans); w[0].push_back(0); int from; LL now; b[0]=-inf;//!!!
26     for(int i=1;i<=n;i++) {
27         from=f[i]-1;
28         for(int j=0,size=w[from].size();j<size;j++) {
29             int v=w[from][j]; if(b[i]<b[v]) continue;//转移不到           
30             cost1[v-1]=cost2[v-1]=0;
31             for(int k=v;k<=i;k++) cost1[k]=abs(b[k]-b[v]),cost2[k]=abs(b[k]-b[i]);
32             for(int k=v+1;k<=i;k++) cost1[k]+=cost1[k-1],cost2[k]+=cost2[k-1];           
33             for(int k=v;k<=i;k++) { 
34                 now=cost1[k]-cost1[v]+cost2[i]-cost2[k]; 
35                 g[i]=min(g[i],g[v]+now);
36             }
37         }
38         w[f[i]].push_back(i);
39     }
40     printf("%lld",g[n]);
41 }
42 
43 int main()
44 {
45     work();
46     return 0;
47 }