CF1699D Almost Triple Deletions 题解

本文主要是介绍CF1699D Almost Triple Deletions 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

可能更好的阅读体验

题目传送门

题目大意

给定一个长度为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\)，每次操作你可以选择相邻的两个不同的数字删去，然后剩下的部分连成一个序列。
现在求让这个序列所以值相等的前提下，序列的最长长度。
多组数据，数据组数 \(T\le 1000\)
\(1\le n\le 5000\)，\(1\le a_i\le n\)，\(\sum n\le 10^4\)

题目解析

考虑 DP，发现很不可做。
由于 \(n\le 5000\)，所以区间 DP 貌似不可做，因为如果是区间 DP 肯定需要枚举断点，不可行。
所以考虑线性 DP，然后枚举转移点 \(O(n^2)\) 做。
由于需要让剩下的数字一样，所以设 \(f_i\) 为前面 \(i\) 个并且第 \(i\) 个一定需要选的答案。

现在问题到了如何判断是否能够转移，也就是判断一段是否能全部删除光。
不难发现结论：一段数组可以删光当且仅当这段数组长度为偶数并且众数的出现次数不超过数组长度一半。
证明是显然的。

有了这个结论，我们可以预处理所有的区间是否能够删除即可。

int n,w[maxn][maxn],f[maxn],a[maxn],t[maxn],ans;
void work(){
	n=read(); int i,j,maxx=-1; for(i=1;i<=n;i++) a[i]=read();
	for(i=1;i<=n;i++) for(j=1;j<=n;j++) w[i][j]=i>j;
	for(i=1;i<=n;i++){
		maxx=-1; for(j=1;j<=n;j++) t[j]=0;
		for(j=i;j<=n;j++){
			t[a[j]]++; maxx=mmax(maxx,t[a[j]]);
			if(maxx<=((j-i+1)>>1)&&((j-i)&1)) w[i][j]=1;
		}
	}
	f[1]=1; for(i=2;i<=n;i++) if(w[1][i-1]) f[i]=1; else f[i]=-INF;
	for(i=1;i<=n;i++) for(j=i-1;j>=1;j-=2) if(a[i]==a[j]&&w[j+1][i-1]) f[i]=mmax(f[i],f[j]+1);
	ans=0; for(i=1;i<=n;i++) if(w[i+1][n]||i+1>n) ans=mmax(ans,f[i]); print(ans),pc('\n'); return;
}

这篇关于CF1699D Almost Triple Deletions 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！