题解 P2501 【[HAOI2006]数字序列】
真是道毒题。 看题解看了2个多小时才看懂，还是对着代码模拟，如图QAQ
楼下紫名大佬发的题解似乎是对大牛写的，我写个通俗易懂的题解，同时附上代码，代码很精巧，不会有太多的解释，建议模拟模拟，理解它。
首先，第一问
直接做不太好做，可以考虑把求最少改动的改为求最多不改动的。
我们用a数组存储n个数，当a[i]和a[j] (i<j)不需要改动时，肯定满足a[j]-a[i]>=j-i , 这个很好理解，a[i],a[j]中间的数至少要比上一个数多1，移项可得a[j]-j>=a[i]-i , 于是可以直接把每个数减去他的位置，即a[i]-=i; 然后求最长不下降子序列就可以了。
复杂的第二问
我们用f[i]表示前i个数要达到单调上升最少改动的幅度（最后答案为f[n]）.
【中心思想】：若a[i],a[j] (i<j) 满足 a[j]-a[i]>=j-i , 那么[i,j]中一定存在一个k,使a[i ~ k]都变成a[i],a[k+1 ~ j]都变成a[j]时，a[i~j]单调上升且代价最小，这个其实可以想出个所以然，但严格的数学证明还是要参考楼下ydc神犇。至于这个k , 直接枚举即可 。 理论时间复杂度为O(n^3) ， 但实际远达不到 ， 加上数据随机 ， 是可以水过的。
好吧，上代码，给少量注释，更多的希望读者自行理解。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;++i)
#define dop(i,m,n) for(int i=m;i>=n;--i)
#define each(i,m,v) for(int i=head[m],v=e[i].to;i;i=e[i].next,v=e[i].to)
#define lowbit(x) (x&(-x))
#define ll long long
#define INF 1073741824
#define re register
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
} //以上一大堆废话
const int maxn=35010;
int n,a[maxn],c[maxn],dp[maxn],len,tmp,num,head[maxn];
ll f[maxn],sum1[maxn],sum2[maxn]; //要开long long寸不然炸
struct Edge{
int to,next;
}e[maxn];
void Add(int from,int to){
e[++num].to=to;
e[num].next=head[from];
head[from]=num;
} //邻接表
int main(){
n=read();
rep(i,1,n) a[i]=read()-i;
rep(i,1,n) c[i]=INF;
c[0]=-INF;dp[1]=1;len=1;a[++n]=INF;c[1]=a[1];a[0]=-INF;
rep(i,2,n){ //仔细思考这个循环，c是一个单调上升的数组，dp[i]表示什么？
tmp=upper_bound(c,c+1+len,a[i])-c;
len=max(len,tmp);
dp[i]=tmp;
c[tmp]=min(c[tmp],a[i]);
}
printf("%d\n",n-dp[n]);
dop(i,n,0) Add(dp[i],i),f[i]=INF;f[0]=0; //f的意义如上，想想这个连边的意义
rep(i,1,n)
each(j,dp[i]-1,to){
if(to>i) break;
if(a[to]>a[i]) continue;
rep(k,to,i) sum1[k]=abs(a[k]-a[to]),sum2[k]=abs(a[k]-a[i]);
rep(k,to+1,i) sum1[k]+=sum1[k-1],sum2[k]+=sum2[k-1]; //前缀和
rep(k,to,i-1) f[i]=min(f[i],f[to]+sum1[k]-sum1[to]+sum2[i]-sum2[k]); //想想前面的【中心思想】
}
printf("%lld\n",f[n]);
return 0;
}