标签：frac 1987F1 mid CodeForces 区间 操作 1987F2 dp

分析

首先显然有 dp 状态 \(g_i\) 表示前 \(i\) 个数，能进行最大的操作次数。
转移有 \(g_i=\max\limits_{j=1}^{i-1} (g_j+\frac{i-j}{2})[2|(i-j)]\)
但这里显然缺少转移条件。
经过基本观察，发现若 \(i\) 操作过，满足条件：

• \(a_i \equiv i (mod\ 2)\)
• \(i\) 左侧操作过 \(\frac{i-a_i}{2}\) 次。

第二条十分关键，这启示我们能否操作只关心前缀。
发现缺少的条件即为经过 \(g_j\) 次操作，\([j,i]\) 区间能否被删完，但是怎么求呢？
再进行基本观察，发现一个点对 \((a_i,a_j)\) 能被操作中间必须被删完。
因此自然地设出状态 \(dp_{l,r,x}\) 表示在 \(l\) 前进行 \(x\) 次操作是否能删除区间 \([i,j]\)。
状态转移方程有：

\[dp_{l,r,x}=dp_{l,mid,x}\ \& \ dp_{mid+1,r,x-\frac{mid-l}{2}}\ \&\ (x\ge \frac{i-a_i}{2}) \]

时间复杂度 \(O(n^4)\)，但是只枚举偶数区间，常数带个 \(\frac{1}{2}\)，可通过 F1。
观察 \(dp\) 数组性质，发现固定区间 \([l,r]\) 后数组呈 \(000...1111...\)，考虑维护第一个 \(1\) 的位置。
原来的状态 \(dp_{l,r}\) 改为删除区间 \([l,r]\)前进行的最少操作次数。
状态转移方程有:

\[dp_{l,r}=\min_{mid} max(\frac{i-a_i}{2},dp_{l,mid},dp_{mid+1,r}-\frac{mid-l}{2}) \]

另外的，如果 \([l+1,r-1]\) 区间能被删除，考虑直接套上一对 \((l,r)\)，具体间代码
此时 \(g_j\) 能转移的条件变为了 \(g_j \ge dp_{j,i}\)。
时间复杂度 \(O(n^3)\)，可通过 F2.

代码

懒得写 F1 的（

void Main(){
	n=rd;
	for(int i=1;i<=n;i++)
		a[i]=rd,g[i]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dp[i][j]=INF;
	for(int len=2;len<=n;len+=2){
		for(int l=1;l+len-1<=n;l++){
			if((l-a[l])&1) continue;
			if(l<a[l]) continue;
			int r=l+len-1;
			if(len==2||dp[l+1][r-1]<=(l-a[l])/2) dp[l][r]=(l-a[l])/2;
			for(int mid=l+1;mid<r;mid+=2){
				dp[l][r]=min(dp[l][r],max((l-a[l])/2,max(dp[l][mid],dp[mid+1][r]-(mid-l+1)/2)));
			}
		}
	}
	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]>=dp[j][i])
				g[i]=max(g[i],g[j-1]+(i-j+1)/2);
	}
	cout<<g[n]<<endl;
}

标签：frac,1987F1,mid,CodeForces,区间,操作,1987F2,dp
From： https://www.cnblogs.com/smilemask/p/18297078