题解：CF1987F2 Interesting Problem (Hard Version)

DaiRuiChen007无敌了！

唐氏区间 dp 拖了一年。

首先按照区间 dp 的基本思路：设

dp_{l,r}

代表

[l,r]

区间的答案。考虑到我们要通过删除前面的数给删除后面的数机会，不妨设

dp_{l,r}

代表删除完

[l,r]

在

[1,l-1]

要至少删除多少个数。

区间 dp 的两种常见转移方式，一种是

dp_{l,r}

从

dp_{l+1,r-1}

转移而来，另外一种是枚举中间断点，从

dp_{l,mid}

和

dp_{mid+1,r}

转移而来。

第一种转移在本题当中，可以看

(l,r)

这对数的删除转移情况，因为是先把

[l+1,r-1]

删完了，所以

(l,r)

在前面删的数的数量必须大于等于

[l+1,r-1]

。

第二种转移直接枚举断点，并排删除

dp_{l,mid}

和

dp_{mid+1,r}

，注意删除

[l,mid]

时候给

[mid+1,r]

的删除带来的影响。

最后用

f_i

转移判断能删多少个数：如果

dp_{\left \{ j|1\le j\le i-1 \right \} ,i}

（要求

[j,i]

长度为偶）的值小于等于

f_{j-1}

，就可以直接删除

[j,i]

转移而来。

时间复杂度

O(n^3)

，

O(n^4)

是什么做法呢？

CPP

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
}
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48); 
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');
}
int n;
int a[817]; 
int dp[817][817];	//dp[i][j] 代表消除完 [i,j] 至少要消除前面多少个数 
int dp1[817];	//dp1[i] 代表最少保留前 i 个数的几个 
//更新：最多删多少个  
void solve(){
	n=read();
	for(int i=1;i<=800;i++){
		for(int j=1;j<=800;j++){
			dp[i][j]=1e18;
		} 
	} 
	for(int i=1;i<=n;i++){
		a[i]=read();
		dp[i][i-1]=0;
		dp1[i]=0; 
	}
	for(int k=2;k<=n;k+=2){
		for(int l=1,r=l+k-1;r<=n;l++,r++){
			//现在转移的是 [l,r] 区间 
			if(l>=a[l]&&(l-a[l])%2==0){
				int now=l-a[l];
				if(dp[l+1][r-1]<=now)	dp[l][r]=now;
			} 
			for(int i=l+1;i<=r;i+=2){
				//dp[l][i] 和 dp[i+1][r] 的连接 
				dp[l][r]=min(dp[l][r],max(dp[l][i],dp[i+1][r]-(i-l+1))); 
			}
//			cout<<'#'<<l<<' '<<r<<' '<<dp[l][r]<<endl;
		}
	}
//	putchar('\n');
	dp1[0]=0;
	for(int i=1;i<=n;i++){
		dp1[i]=dp1[i-1];
//		dp1[i]=dp1[i-1]+1;	//第一种转移方案 
		for(int j=i-1;j>=1;j-=2){
			if(dp1[j-1]>=dp[j][i]){
				dp1[i]=max(dp1[i],dp1[j-1]+(i-j+1));
//				cout<<'!'<<i<<' '<<j<<' '<<dp1[j-1]+(i-j+1)<<endl;
			}
		} 
	}
	write2(dp1[n]/2);
	return;
}
signed main(){
	int T=read();
	while(T--)	solve();
	return 0;
}//一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的。

题解：CF1987F2 Interesting Problem (Hard Version)

文章操作

相关推荐

评论

题解：CF1987F2 Interesting Problem (Hard Version)