1234F

传送门

题意：
给出一个只含 a~t 的字符串，现在可以选择一段区间进行翻转，问区间中字符各不相同时，最长长度为多少。

分析：
将题意转换为选择两个字符各不相同的区间，然后长度相加取最大；
字符串中满足条件的所有区间长度和不超过20∗n，那么处理出所有区间，现在任务即为找到两个区间，其字符各不相同，且长度和最大；

dp[i] 代表，最多（至多）出现这些字符 的 连续串 的 最大长度
i是二进制状态枚举

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+5;;
const int inf=0x3f3f3f3f;
#define ls (i<<1)
#define rs (i<<1|1)
#define fi first
#define se second
LL read()
{
    LL x=0,t=1;
    char ch=getchar();
    while(!isdigit(ch)){ if(ch=='-')t=-1; ch=getchar(); }
    while(isdigit(ch)){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*t;
}
int f[(1<<20)+5];
char s[N];
int main()
{
    scanf("%s",s);
    int n=strlen(s);
    int lim=(1<<20)-1;
    for(int i=0;i<n;i++)
    {
        int t=0;
        for(int j=i;j<n;j++)
        {
            int v=s[j]-'a';
            if(t&(1<<v) ) break;
            t|=1<<v;
            f[t]=j-i+1;  ///不重复连续串的最长长度，不懂试着模拟
            //printf("%d
",f[t] );
        }
    }
    for(int i=0;i<20;i++)
        for(int j=0;j<=lim;j++)
            if( (j&(1<<i) )==0)
                f[j|(1<<i)]=max(f[j|(1<<i)],f[j] );///如果s中没有这些连续串，那么就等于f[j]，便于后面通过互斥快速算答案
    int ans=0;
    for(int i=0;i<=lim;i++)
        ans=max(ans,f[i]+f[lim-i] );
    printf("%d
",ans);
}