FZU2218 Simple String Problem(状压DP)

时间:2021-04-19 15:22:40

首先,定义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[<<];
int main(){
int t,n,k;
char str[];
scanf("%d",&t);
while(t--){
scanf("%d%d%s",&n,&k,str);
memset(d,,sizeof(d));
for(int i=; i<n; ++i){
int s=;
for(int j=i; j<n; ++j){
s|=<<str[j]-'a';
d[s]=max(d[s],j-i+);
}
}
for(int i=; i<(<<k); ++i){
for(int j=; j<k ;++j){
if((i>>j)&) d[i]=max(d[i],d[i&(~(<<j))]);
}
}
int res=;
for(int i=; i<(<<k); ++i){
res=max(res,d[i]*d[(~i)&((<<k)-)]);
}
printf("%d\n",res);
}
return ;
}