CF1987F2 Interesting Problem (Hard Version) 做题记录

对于一个长 $n$ 的序列 $a$，你可以选择一个满足 $a_i=i$ 且 $i<n$ 的位置 $i$ 并删除 $a_i$ 和 $a_{i+1}$，删除后两边会拼接。

给定一个长 $n$ 的序列 $a$，求最多能进行多少次上述操作。

$1\le n\le 800$，$1\le a_i\le n$。

不会 *2600。

删除的过程不好刻画，考虑某个位置 $a_i$ 和与它一起被删去的位置 $a_j$（$i<j$），显然 $a_{[i+1,j-1]}$ 都要被删去，且它们一定先于 $(a_i,a_j)$ 被删去。

这启发我们设计状态：$f_{l,r}$ 表示完全删除 $a_{[l,r]}$ 至少需要在 $[1,l-1]$ 中执行多少次删除操作。

转移考虑枚举和 $a_l$ 一起删去的 $a_k$。显然 $l<a_l$ 或者 $l\not\equiv a_l\pmod 2$ 则 $a_l$ 就无法被删去，否则设 $v=\frac{l-a_l}{2}$。由于 $a_l$ 和 $a_k$ 一起删除，所以 $a_{[l+1,k-1]}$ 前面最多能执行 $v$ 次操作，故要求 $f_{l+1,k-1}\le v$，此时有 $\max(v,f_{k+1,r}-\frac{k-l+1}{2})\to f_{l,r}$。

边界为 $f_{i+1,i}=0$。

求答案是简单的，设 $g_i$ 表示 $a_{[1,i]}$ 中最多执行多少次操作，利用 $f$ 转移即可。

时间复杂度 $O(n^3)$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=805,inf=1e8;

int n,a[S];
int f[S][S],g[S];

inline void slove()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=0;i<=n;i++) f[i+1][i]=0;
	for(int len=2;len<=n;len+=2)
		for(int l=1;l<=n-len+1;l++)
		{
			int r=l+len-1;
			f[l][r]=inf;
			if(l>=a[l]&&(l-a[l]&1^1))
			{
				int val=(l-a[l])/2;
				for(int k=l+1;k<=r;k+=2)
					if(f[l+1][k-1]<=val)
					{
						int pre=max(
							val,
							f[k+1][r]-(k-l+1)/2
						);
						f[l][r]=min(f[l][r],pre);
					}
			}
		}
	g[0]=0;
	for(int i=1;i<=n;i++)
	{
		g[i]=g[i-1];
		for(int j=i-1;j>=1;j-=2)
			if(g[j-1]>=f[j][i]) g[i]=max(g[i],g[j-1]+(i-j+1)/2);
	}
	cout<<g[n]<<'\n';
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T-->0) slove();
	return 0;
}