这种不基于状压的方法是对的吗?
每次往前暴力跳,每一步贪心选择最近的位置。
由于颜色有 V 种,依据抽屉原理,只会跳 O(N×V2) 步。
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int a[N],ne[N][25],last[N][25];
bool vis[25];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
for(int j=1;j<=20;j++)last[i][j]=last[i-1][j];//上一项最近位置
last[i][a[i]]=i;
for(int j=1;j<=20;j++)ne[i][j]=ne[i-1][j];//上一项的上一项
ne[i][a[i]]=last[i-1][a[i]];
int r=ne[i][a[i]]-1;
memset(vis,0,sizeof(vis));
vis[a[i]]=1;
for(int j=1;j<=20;j++)
{
if(r<0)break;
ans=max(ans,j*2);
int mx=0,id=0;
for(int k=1;k<=20;k++)
{
if(ne[r][k]>mx&&!vis[k])
{
mx=ne[r][k];
id=k;
}
}
r=mx-1;
vis[id]=1;
}
}
//cout<<'\n';
cout<<ans<<'\n';
return 0;
}