ABC381F
  • 板块学术版
  • 楼主HasNoName
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/22 22:28
  • 上次更新2024/11/23 10:07:11
查看原帖
ABC381F
847051
HasNoName楼主2024/11/22 22:28

这种不基于状压的方法是对的吗?

每次往前暴力跳,每一步贪心选择最近的位置。

由于颜色有 VV 种,依据抽屉原理,只会跳 O(N×V2)O(N\times V^2) 步。

#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;
}

记录

2024/11/22 22:28
加载中...