题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1049
题意：给出一个数列A，要求：（1）修改最少的数字使得数列严格递增；（2）在（1）的基础上使得修改的绝对值之和最小。
思路：对于第一问看起来像是求最长上升子 列，其实不是。我们想，若对于i<j，j能由i转移过来，那么需满足A[j]-A[i]>=j-i才行，这样我们发现只要A[j]-j>=A[i]-i即可。因此令A[i]=A[i]-i，这样求LIS即可。对于第二问，若i<j且j由i转移过来，那么[i+1,j-1]之间 的数字或者大于A[j]或者小于A[i]，最后这段区间的数字必然是前面一段修改为A[i]后面一段修改为A[j]。因此，记录每个位置j由哪些前面的位置转移过来，直接暴力枚举前面的位置i即可。然后对于[i+1,j-1]，暴力枚举中间的分界点。
int a[N],b[N],c[N],n,f[N];
vector<int> V[N];
int S[N],M; int find(int x)
{
int low=1,high=M,mid;
while(low<=high)
{
mid=(low+high)>>1;
if(b[mid]==x) return mid;
if(b[mid]<x) low=mid+1;
else high=mid-1;
}
} void add(int x,int y)
{
while(x<=n) upMax(S[x],y),x+=x&-x;
} int get(int x)
{
int ans=0;
while(x) upMax(ans,S[x]),x-=x&-x;
return ans;
} int Ans; void deal1()
{
int i;
a[++n]=INF;
FOR1(i,n) b[i]=a[i];
sort(b+1,b+n+1);
M=unique(b+1,b+n+1)-(b+1);
FOR1(i,n) c[i]=find(a[i]);
Ans=0;
FOR1(i,n)
{
f[i]=get(c[i])+1;
add(c[i],f[i]);
upMax(Ans,f[i]);
}
PR(n-Ans);
} i64 sum1[N],sum2[N],dp[N]; void deal2()
{
int i,j,k,t;
V[0].pb(0);
FOR1(i,n) V[f[i]].pb(i),dp[i]=inf;
a[0]=-INF; dp[0]=0;
FOR1(i,n)
{
FOR0(j,SZ(V[f[i]-1]))
{
k=V[f[i]-1][j];
if(k>i) break;
if(a[k]>a[i]) continue;
for(t=k;t<=i;t++) sum1[t]=abs(a[t]-a[k]),sum2[t]=abs(a[t]-a[i]);
for(t=k+1;t<=i;t++) sum1[t]+=sum1[t-1],sum2[t]+=sum2[t-1];
for(t=k;t<i;t++) upMin(dp[i],dp[k]+sum1[t]+sum2[i]-sum2[t]);
}
}
PR(dp[n]);
} int main()
{
RD(n);
int i;
FOR1(i,n) RD(a[i]),a[i]-=i;
deal1(); deal2();
}