关于 WA on #11

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define int long long
#define pb emplace_back
#define il inline
using namespace std;

const int MAXN=3.5e4+5;
int n,a[MAXN],b[MAXN];
vector <int> las[MAXN];
int ssy[MAXN],l[MAXN],f[MAXN],pre[MAXN],suf[MAXN];

template <typename T>
il T _abs(T x) {return x>0 ? x : -x;}

signed main()
{
	ios::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
	
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i],b[i]=a[i]-i;
	b[0]=-1e16,b[++n]=1e16;
	
	int len=0,ind;
	for(int i=1;i<=n;++i)
	{
		if(b[i]>=ssy[len]) ssy[++len]=b[i],las[len].pb(i),l[i]=len;//,cerr<<"pb "<<len<<' '<<i<<'\n';
		else 
		{
			ind=upper_bound(ssy+1,ssy+len+1,b[i])-ssy;
			ssy[ind]=b[i];
			las[ind].pb(i);
			//cerr<<"pb "<<ind<<' '<<i<<'\n';
			l[i]=ind;
		}
	}
	
	las[0].pb(0);
	
	cout<<n-len<<'\n';
	
	//for(int i=1;i<=n;++i) cerr<<l[i]<<' '; cerr<<'\n';
	
	memset(f,0x7f,sizeof(f));
	f[0]=0;
	
	for(int i=1;i<=n;++i) for(auto j:las[l[i]-1])
	{
		if(j>i || b[j]>b[i]) continue;
		
		//cerr<<"------------ "<<i<<' '<<j<<'\n';
		
		pre[j]=suf[i-1]=0;
		for(int k=j+1;k<i;++k) pre[k]=pre[k-1]+_abs(b[k]-b[j]);
		for(int k=i-2;k>=j;--k) suf[k]=suf[k+1]+_abs(b[k+1]-b[i]);
		
		for(int k=j;k<i;++k) f[i]=min(f[i],f[j]+pre[k]+suf[k]); 
		
		//for(int k=j;k<i;++k) f[i]=min(f[i],f[j]+abs(gs(j,k)-(k-j+1)*b[j])+abs(gs(k+1,i)-(i-k)*b[i])),cerr<<k<<" : "<<f[j]<<' '<<abs(gs(j,k)-(k-j+1)*b[j])<<' '<<abs(gs(k+1,i)-(i-k)*b[i])<<'\n';
	}
	
	//cerr<<"{f} "; for(int i=1;i<=n;++i) cerr<<f[i]<<' '; cerr<<'\n';
	
	//if(f[n]<0) {cout<<"596989102"; return 0;} //这个是特判的 #11 的第二问答案
	cout<<f[n];
	
	return 0;
}