题解：AT_abc381_f [ABC381F] 1122 Subsequence

首先

a

的值域很小只有

20

，可以支持

2^{20}

，考虑用状压 dp。

状态

s

，当

s

二进制下后面第

i

为

1

时，表示

i

计算在答案中。

s

的贡献为

2\times \lvert s\rvert

。

设

f(s)

表示状态为

s

时，右端点的最小值。当

f(s) \le n

时说明

s

合法，可以贡献答案。

f(s)

只能由

t=s-2^{i}

的

f(t)

转移过来，显然

f(s)

是

f(t)

后面的第二个

i

的位置。若不存在第二个

i

，令

f(s)=n+1

表示不合法。设

ne(i,j)

表示数组

a

在

[i+1,n]

中第一个

j+1

的位置，则有

\displaystyle f(s)=\min_{0 \le i < \lvert s\rvert}(ne(ne(f(t),i),i))

。

预处理所有

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

题解：AT_abc381_f [ABC381F] 1122 Subsequence

文章操作

相关推荐

评论

题解：AT_abc381_f [ABC381F] 1122 Subsequence