思路是把原序列处理成 0 尽量少的情况然后以 0 为分界线分割多组，然后区间 DP，时间复杂度大概是 $O($组数$^2 \times n\log n)$，Subtask 4 T了一个点，靠特判过了(

这个思路有什么可以优化的地方吗？或者说正解和这个思路无关？

代码：

#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=1e6+10;
struct node{
	int val,id;
	inline bool operator<(const node &k)const{
		return val>k.val;
	}
};
struct heap{
	node h[maxn];
	int l;
	inline void push(node k){
		h[++l]=k;
		int f,s=l;
		while(f=s>>1){
			if(h[s]<h[f])swap(h[f],h[s]);
			else break;
			s=f;
		}
	}
	inline int size(){return l;}
	inline node top(){return h[1];}
	inline void pop(){
		h[1]=h[l--];
		int f=1,s;
		while((s=f<<1)<=l){
			if(h[s|1]<h[s])s|=1;
			if(h[s]<h[f])swap(h[f],h[s]);
			else break;
			f=s;
		}
	}
}q;
int a[maxn],n;
ll ans;
#define fi first
#define se second
typedef pair<int,int> pii;
#define pb push_back
vector<pii>s;
ll f[1010][1010];
inline int calc(int l,int r){
	while(q.size())q.pop();
	for(ri i=l;i<=r;++i)q.push({a[i]+i,i});
	int ret=INT_MAX;
	for(ri i=l,p=l;i<=r;++i){
		if(a[i]>a[p]+i-p)p=i;
		while(q.size()&&q.top().id<=i)q.pop();
		if(q.size())ret=min(ret,max(a[p]+i-p,q.top().val-i));
		else ret=min(ret,a[p]+i-p);
	}
	return ret;
}
int main(){
	scanf("%d",&n);
	for(ri i=1;i<=n;++i)scanf("%d",a+i);
	for(ri i=n,p=n;i;--i){
		if(a[i]>a[p]+i-p)p=i;
		else a[i]=a[p]+i-p;
	}
	for(ri i=1,p=1;i<=n;++i){
		if(a[i]>a[p]+p-i)p=i;
		else a[i]=a[p]+p-i;
	}
	ri p=1;
	while(p<=n){
		while(p<=n&&!a[p])++p;
		if(p>n)break;
		ri nxt=p+1;
		while(nxt<=n&&a[nxt])++nxt;
		f[s.size()][s.size()]=calc(p,nxt-1);
		s.pb({p,nxt-1});
		p=nxt;
	}
	for(ri len=2;len<=s.size();++len)
		for(ri i=0;i+len-1<s.size();++i){
			ri j=i+len-1;
			f[i][j]=calc(s[i].fi,s[j].se);
			for(ri k=i;k<j;++k)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
		}
	printf("%lld",f[0][s.size()-1]);
	return 0;
}