先来看第一问。
发现直接做要考虑两数中间的数能否变得合法，所以按套路将 (a_i) 减去 (i)，这样就只要变成单调不降，只要两数合法中间的数就一定能变得合法。考虑不改变的那些数，它们一定单调不降，所以答案就是序列总长度减去最长不降子序列的长度。
接下来看第二问。
- 可能有多个最长不下降子序列，每个子序列的答案都有可能成为最小值。
- 子序列中相邻的两项之间的任意一个数要不小于前一项，要不大于后一项，否则将其并入子序列长度会更长。
现在我们有两个相邻的数，都需要修改，前者大于后者。显然，将它们修改成两数之间的任意一个数代价都是最小的。应用到子序列的相邻两项 (i) 和 (j) 之间，假设某种情况第 (k) 个数修改成了 (b_k)，将相同数合并，那么我们就得到了一个新的序列 (b)。考虑相邻的三项 (x,y,z(ileq x<x+1=y<y+1=zleq j,b_x<b_y<b_z))，我们将 (b_y) 修改成 (b_x) 或 (b_z)，一定有一种能保证代价不变或减小。那这样一直搞下去最终只会剩下 (i) 和 (j) 这两项，所以我们就得到了一个结论：最优解一定存在一个断点 (k)，使得 (b_i=b_kleq b_{k+1}=b_j)。
然后用这个结论直接搞就行了，时间复杂度 (O(n^3))，但数据好像是随机的所以根本跑不满。
code:
#include<bits/stdc++.h>
using namespace std;
#define N 35005
#define NN 135005
#define Min(x,y)((x)<(y)?x:y)
#define Max(x,y)((x)>(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
#define lowbit(x)((x)&-(x))
#define int long long
const int LIM=100000,FAT=35000;
vector<int>vec[N];
int c[NN],d[NN],a[N],f[N],g[N];
void add(int x,int v)
{
while(x<=LIM+FAT)c[x]=Max(c[x],v),x+=lowbit(x);
}
int sum(int x)
{
int v=0;
while(x)v=Max(v,c[x]),x-=lowbit(x);
return v;
}
signed main()
{
int n,i,j,ret,mn,k,pos;
scanf("%lld",&n);
For(i,1,n)
{
scanf("%lld",&a[i]);
a[i]-=i;
f[i]=sum(a[i]+FAT)+1;
add(a[i]+FAT,f[i]);
vec[f[i]].push_back(i);
}
printf("%lld
",n-sum(LIM+FAT));
vec[0].push_back(0);
f[n+1]=sum(LIM+FAT)+1;
a[n+1]=LONG_LONG_MAX>>15;
a[0]=LONG_LONG_MIN>>15;
For(i,1,n+1)
{
g[i]=LONG_LONG_MAX>>15;
For(j,0,vec[f[i]-1].size()-1)
{
pos=vec[f[i]-1][j];
if(pos>i)break;
else if(a[pos]<=a[i])
{
ret=0;
For(k,pos+1,i-1)ret+=llabs(a[k]-a[i]);
mn=ret;
For(k,pos+1,i-1)ret-=llabs(a[k]-a[i])-llabs(a[k]-a[pos]),mn=Min(mn,ret);
g[i]=Min(g[i],g[pos]+mn);
}
}
}
printf("%lld",g[n+1]);
return 0;
}