Description：

把一个序列变成单调上升的，在最小化修改位置的前提下最小化修改的差的和。

$1\leqslant n \leqslant35000$

Solution：

设 $b[i]=a[i]-i$ ，先求出 $b$ 的单调不降子序列，然后转移就是 $g[i]=g[j]+w(j+1,i)(f[i]=f[j]+1)$ ，关于 $w(j+1,i)$ 怎么求， $a[i](i\in[j+1],i)$ 一定大于 $a[i]$ 或者小于 $a[j]$ ，否则会形成一个新的上升序列，然后有一个性质就是最后一定存在一个 $k$ ，使得 $[j+1,k]$ 最后都被修改成了 $a[j]$ ，其他的被修改成了 $a[i]$ ，于是前缀和一下再枚举 $k$ 就被卡成 $90$ 分了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

#define MAXN 35010

int a[MAXN];

typedef long long ll;

int f[MAXN];

ll g[MAXN],s1[MAXN],s2[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int main()

{

	scanf("%d",&n);

	for(register int i = 1;i <= n;++i)

	{

		a[i] = read();g[i] = 0x3f3f3f3f3f3f3f3f;

	}

	a[++n] = 0x3f3f3f3f;g[n] = 0x3f3f3f3f3f3f3f3f;

	for(register int i = 1;i <= n;++i)

	{

		f[i] = 1;

		for(register int j = 1;j < i;++j)

		{

			if(a[i] - i >= a[j] - j)

			{

				f[i] = max(f[i],f[j] + 1);

			}

		}

	}

	for(register int i = n;i >= 0;--i)add(f[i],i);

	for(register int i = 1;i <= n;++i)

	{

		for(register int j = lin[f[i] - 1];j != 0;j = e[j].nxt)

		{

			if(e[j].to >= i)break;

			if(a[i] - i >= a[e[j].to] - e[j].to)

			{

				s1[e[j].to] = s2[e[j].to] = 0;

				for(register int k = e[j].to + 1;k <= i;++k)

				{

					s1[k] = s1[k - 1] + abs((a[k] - k) - (a[e[j].to] - e[j].to));

					s2[k] = s2[k - 1] + abs((a[k] - k) - (a[i] - i));

				}

				for(register int k = e[j].to + 1;k <= i;++k)

				{

					g[i] = min(g[i],g[e[j].to] + s1[k - 1] + s2[i] - s2[k - 1]);

				}

			}

		}

	}

	printf("%d\n%lld\n",n - f[n],g[n]);

	return 0;

}