本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-03 15:56:48

首先考虑F1。容易想到区间dp。发现在dp的时候区间前面删了几个元素也是非常重要的，所以把它加入状态。

设 $f_{l,r,x}$ 代表 $[l,r]$ 区间在 $[1,l)$ 已经删了最多 $x$ 个的前提下能够进行的操作数。

转移有两方面，一方面是两个区间合并，这时 $f_{l,r,x}=\min_{k=l}^{r-1}\max(f_{l,k,x},f_{k+1,r,x+f_{l,k,x}*2})$ 。

因为前半段区间会影响到后半段，所以后半段可以增加前面删除的个数。

第二方面的转移是对第一个元素进行操作，需要满足 $a_l=l-x\land 2f_{l+1,r,x}<r-l$ ，即一定要先对右边区间删后再对 $l$ 操作，且区间内一定要有剩余元素。

因为状态是最多，所以 $f_{l,r,x}$ 也要向 $f_{l,r,x+2}$ 转移。

第三维只会是偶数，因为每次删除删两个。

但存储的是进行的操作次数，所以在一些时候需要乘二。

（前面半句有点难发现，因为这个调了好久）

$\mathrm{O(n^3)}$ 的状态和 $\mathrm{O(n)}$ 的转移，总体来说是 $\mathrm{O(n^4)}$ 。

code (F1)

const int N=1e2+5;

int a[N];

int f[N][N][N];

signed main(){
	signed _T=read();
	while(_T--){
		int n=read();
		for(int i=1;i<=n;i++)
			a[i]=read();
		for(int len=2;len<=n;len++){
			for(int l=1;l+len-1<=n;l++){
				int r=l+len-1,mx=0;
				for(int x=0;x<=l-1;x+=2){
					f[l][r][x]=max(mx,f[l+1][r][x]+(a[l]==l-x&&f[l+1][r][x]*2!=r-l));
					for(int k=l;k<r;k++)
						f[l][r][x]=max(f[l][r][x],f[l][k][x]+f[k+1][r][x+f[l][k][x]*2]);  
					mx=max(mx,f[l][r][x]);
				}
			}
		}print(f[1][n][0]),pc('\n');
	}
	return 0;
}

然后考虑优化。发现（最好能）对于一个区间，其前面能够被删除的数越多越好，因为自己不会影响前面。

那么考虑记录这个而非区间内最大操作次数，代价是不能对操作数量计数，这里有一个套路是固定使区间删完，然后再用一个dp来合并答案。

那么状态是 $f_{l,r}$ 表示若想吧 $[l,r]$ 删完，$[1,l)$ 最少进行几次操作。

转移也是两方面，合并和第一个元素进行操作。

合并是简单的，$f_{l,r}=\min_{k=l}^{r-1} \max(f_{l,k},f_{k+1,r}-\frac{k-l+1}{2})$ 。

因为可以先对左边操作，右边所需要的就可以相应减少。

若是对 $l$ 进行操作则需满足 $\frac{l-a_l}{2}\geq f_{l+1,r-1}\land l\equiv a_l\pmod{2} $ 。

同样需要注意前者，需要先删里面才能删外面。

初始值设为无穷大。

这样状态就缩减到了 $\mathrm{O(n^2)}$ ，总复杂度 $\mathrm{O(n^3)}$ 。

后面的合并答案写了一个傻傻的 $\mathrm{O(n^3)}$ dp，但能过。

好像只需要设 $g_i$ 表示前 $i$ 项最多进行 $g_i$ 次操作就行了。

code

const int N=8e2+5;

int a[N];

int f[N][N];

int ans[N][N];

signed main(){
	signed _T=read();
	while(_T--){
		int n=read();
		for(int i=1;i<=n;i++)
			a[i]=read();
		for(int len=2;len<=n;len+=2){
			for(int l=1;l+len-1<=n;l++){
				int r=l+len-1;
				f[l][r]=inf;
				if(a[l]<=l&&a[l]%2==l%2&&f[l+1][r-1]<=(l-a[l])\/2)
					f[l][r]=(l-a[l])\/2;
				for(int k=l+1;k<r;k+=2)
					f[l][r]=min(f[l][r],max(f[l][k],f[k+1][r]-(k-l+1)\/2));
			}
		}
		int mx=0;
		ans[0][0]=0;
		for(int i=1;i<=n;i++)
			ans[0][i]=-inf;
		for(int i=1;i<=n;i++){
			for(int j=0;j<=n;j++){
				ans[i][j]=ans[i-1][j];
				for(int l=i-1;l>=1;l-=2){
					if(f[l][i]<=j-(i-l+1)\/2)
						ans[i][j]=max(ans[i][j],ans[l-1][j-(i-l+1)\/2]+(i-l+1)\/2);
				}
				mx=max(mx,ans[i][j]);
			}
		}print(mx),pc('\n');
	}
	return 0;
}