题解：AT_abc381_f [ABC381F] 1122 Subsequence
zhouruoheng
·
·
题解
首先 a 的值域很小只有 20，可以支持 2^{20}，考虑用状压 dp。
状态 s，当 s 二进制下后面第 i 为 1 时，表示 i 计算在答案中。s 的贡献为 2\times \lvert s\rvert。
设 f(s) 表示状态为 s 时，右端点的最小值。当 f(s) \le n 时说明 s 合法，可以贡献答案。
预处理所有 $ne(i,j)$ 还是比较好办的，直接看代码吧。
``` cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=20,S=1<<20;
int n;
int a[N],ne[N][M];
int f[S];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<M;i++) ne[n][i]=ne[n+1][i]=n+1;
for(int i=n-1;i>=0;i--)
{
for(int j=0;j<M;j++) ne[i][j]=ne[i+1][j];
ne[i][a[i+1]-1]=i+1;
}
for(int i=0;i<S;i++) f[i]=n+1;
f[0]=0;
int ans=0;
for(int i=0;i<S;i++)
{
int cnt=0;
for(int j=0;j<M;j++)
if(i&(1<<j))
{
cnt+=2;
f[i]=min(f[i],ne[ne[f[i^(1<<j)]][j]][j]);
}
if(f[i]<=n) ans=max(ans,cnt);
}
cout<<ans<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
solve();
return 0;
}
```