FZU2218 Simple String Problem（状压DP）

首先，定义S，表示前k个字符出现的集合，用二进制来压缩。

接下来，推出dp1[S]，表示集合为S的子串的最长长度。

然后根据dp1[S]再推出dp2[S]，表示集合为S或S的子集的子串的最长长度。

最后答案就是max(dp2[S]*dp2[补(S)])

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int d[1<<16];
int main(){
    int t,n,k;
    char str[2222];
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%s",&n,&k,str);
        memset(d,0,sizeof(d));
        for(int i=0; i<n; ++i){
            int s=0;
            for(int j=i; j<n; ++j){
                s|=1<<str[j]-'a';
                d[s]=max(d[s],j-i+1);
            }
        }
        for(int i=0; i<(1<<k); ++i){
            for(int j=0; j<k ;++j){
                if((i>>j)&1) d[i]=max(d[i],d[i&(~(1<<j))]);
            }
        }
        int res=0;
        for(int i=0; i<(1<<k); ++i){
            res=max(res,d[i]*d[(~i)&((1<<k)-1)]);
        }
        printf("%d
",res);
    }
    return 0;
}