题目描述
现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。
输入输出格式
输入格式：
第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。
输出格式：
第一行一个整数表示最少需要改变多少个数。
第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。
输入输出样例
输出样例#1：
1
4
思路：
一道 题
（1）第一问
假设第i,j(i<j)两点同时存在，那么必定满足a[j]-a[i]>=j-i
移项发现a[j]-j>=a[i]-i
随后我们将每个a[i]-=i，然后去求a的最长不下降序列长度即可，用总长度n减去这个长度就是答案
最长不下降序列很显然要用nlogn的时间复杂度去搞
（2）第二问
设f[i]为前i为为严格升序序列的最小代价
有一个结论，就是区间（i，j）变为升序序列的最小代价为在（i，j）之间找一个k，
将a[i~k] 都变成a[i],将a[k+1~j] 都变成a[j]，这之间的最小值就是这个区间内的最优代价
然后直接暴力即可
理论实践复杂度为O(n^3)，但是由于第二重循环在随机数据项可能什么都没有，所以实际复杂度应远小于O(n^3)
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#define inf 19999999999;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define yx(k,x) for(int k=fir[x];k;k=nxt[k])
using namespace std;
int dp[36000],c[36000],a[36000],n,len,f[36000],sum1[36000],sum2[36000],fir[36000],nxt[36000],to[36000],tot;
void ade(int x,int y){
to[++tot]=y;
nxt[tot]=fir[x];
fir[x]=tot;
}
signed main(){
scanf("%lld",&n);a[++n]=inf; a[0]=-inf;
rep(i,1,n-1){
scanf("%lld",&a[i]),a[i]-=i;
c[i]=inf;
}c[0]=-inf;len=1,c[1]=a[1];dp[1]=1;
rep(i,2,n){
int zlk=upper_bound(c,c+1+len,a[i])-c;
len=max(len,zlk);
dp[i]=zlk;
c[zlk]=min(c[zlk],a[i]);
}
rep(i,0,n){f[i]=inf;ade(dp[i],i);}f[0]=0;
rep(i,1,n){
yx(j,dp[i]-1){
if(to[j]>i) continue;
if(a[to[j]]>a[i]) continue;
rep(k,to[j],i) sum1[k]=abs(a[k]-a[to[j]]),sum2[k]=abs(a[k]-a[i]);
rep(k,to[j],i-1) sum1[k+1]+=sum1[k],sum2[k+1]+=sum2[k];
rep(k,to[j],i-1) f[i]=min(f[i],f[to[j]]+sum1[k]+sum2[i]-sum2[k]);
}
}
printf("%lld
%lld",n-dp[n],f[n]);
return 0;
}