本文共 1606 字，大约阅读时间需要 5 分钟。

预处理$f[i][j]$表示$[i,j]$能取到的最长区间

枚举第一个区间的左端点,往右一直尺取

一旦发现有颜色出现两次跳出循环

否则加入一个新颜色,把数组的这些颜色位置都标记一下代表第二个段不能选

那么第二个段只能选连续$0$的

我们可以$O(n)$扫描一编,可以得到若干个极长的$0$段

由$f$数组我们就可以知道第二段的最大长度

最坏复杂度$O(n^3)$,不过剪枝比较多,实际上还跑的很快

#include 
   
    using namespace std;const int maxn = 1e3+10;int n,t,a[maxn],li[maxn];int f[maxn][maxn],vis[maxn],r[maxn],casenum,top;vector
    
     vec[maxn];void read(){
   	scanf("%d",&n);	for(int i=1;i<=n;i++)	scanf("%d",&a[i]),li[i] = a[i];	sort( li+1,li+1+n );	top = unique(li+1,li+1+n)-li-1;	for(int i=1;i<=n;i++)	a[i] = lower_bound(li+1,li+1+top,a[i])-li;	}void initF(){
   	memset( f,0,sizeof f );	for(int i=1;i<=n;i++)	{
   		memset( vis,0,sizeof vis );		for(int j=i;j<=n;j++)		{
   			if( vis[a[j]] )	break;			vis[a[j]] = 1, f[i][j] = j-i+1;		}	}	for(int l=2;l<=n;l++)	for(int i=1,j=i+l-1;j<=n;i++,j++)		f[i][j] = max( f[i][j],max(f[i+1][j],f[i][j-1]) );}int main(){
   	int t; cin >> t;	while( t-- )	{
   		read();			for(int i=1;i<=n;i++)	vec[a[i]].push_back( i );		initF();		int ans = 0;		for(int i=1;i<=n;i++)		{
   			if( n-i+1<=ans )	break;			memset( vis,0,sizeof vis );			memset( r,0,sizeof r );			for(int j=i;j<=n;j++)			{
   				if( vis[a[j]] )	break;				vis[a[j]] = 1;				for( auto v:vec[a[j]] )	r[v] = 1;//标记为不可选择				int now = 0, l = j+1;				for(int q=j+1;q<=n;q++)				{
   					if( !r[q] )	now = max( now,f[l][q] );					else	l = q+1;				} 				ans = max( ans,j-i+1+now );			}		}		printf("Case #%d: %d\n",++casenum,ans);		memset( vis,0,sizeof vis ); memset( r,0,sizeof r );		for(int i=1;i<=n;i++)	vec[i].clear();	}}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116020637 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！