题意
有一个序列，要求修改尽可能少的数，使得这个序列变成单调上升序列。输出最少需要修改多少个数，以及在修改最少的前提下，每个数改变的绝对值之和的最小值。
序列长度 $N\le 35000$ 。
题解
子问题1
如果只是单调不降就很简单，但这题要求单调上升。
假设可以保留 $S_i,S_j \ (i < j)$ ，则需要满足 $S_j - S_i \geq j-i$ ，即 $S_j - j\geq S_i-i$ 。
令新序列 $F_i = S_i - i$ ，那么单调不降的部分就可以保留。答案即为 $N -$ 最长不降序列长度。
子问题2
还是假设保留 $F_i,F_j$ ，这时需要将 $[i+1,j-1]$ 的数改成单调不降的。
可以证明最优解一定是找到一个位置 $k$ ，把 $[i,k]$ 的数都变成 $F_i$ ；$[k+1,j]$ 的数都变成 $F_j$ 。
设以 $i$ 结尾的最长不降子序列长度为 $mx[i]$ 。如果确定了 $F_j$ ，那么 $F_i$ 一定满足
$$\begin{cases} i < j \\ F_i \le F_j \\ mx[i]+1=mx[j]\end{cases}$$
对于满足条件的关系 $(i,j)$ 可以在解决子问题1时连边 $mx[i]\rightarrow i$ ，然后遍历所有以 $mx[j]-1$ 为起点的边，再判断是否满足前两个条件即可。
因为所有的最大值也需要被处理，所以令 $F_{N+1}=\inf$ ，然后把序列看成 $N+1$ 个数。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
struct Edge {
int next,to;
} edge[35005];
long long f[35005],l[35005],r[35005];
int cnt,head[35005],n,s[35005],mx[35005];
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
signed main()
{
n=read();
for (int i=1;i<=n;i++) s[i]=read()-i;
s[++n]=1e9; s[0]=-1e9;
int len=0;
add(0,0); add(1,1);
f[mx[1]=++len]=s[1];
for (int i=2;i<=n;i++)
{
if (s[i]>=f[len]) f[mx[i]=++len]=s[i];
else
{
int p=upper_bound(f+1,f+len+1,s[i])-f;
f[mx[i]=p]=s[i];
}
add(mx[i],i);
}
printf("%d\n",n-len);
memset(f,0x3f,sizeof(f));
f[0]=0;
for (int x=1;x<=n;x++)
{
for (int i=head[mx[x]-1];i;i=edge[i].next)
{
int y=edge[i].to;
if (y>x || s[y]>s[x]) continue;
l[y]=0;
for (int j=y+1;j<=x;j++) l[j]=l[j-1]+abs(s[j]-s[y]); //前缀和
r[x]=0;
for (int j=x-1;j>=y;j--) r[j]=r[j+1]+abs(s[j]-s[x]); //后缀和
for (int j=y;j<x;j++) f[x]=min(f[x],f[y]+l[j]+r[j+1]);
}
}
printf("%lld",f[n]);
system("pause");
return 0;
}