FZU 2218【状压】

利用异或取反得最大值。

#include<cstdio>#include<string.h>#include<algorithm>using namespace std;const int N=1<<16;char s[2010];int dp[N];int n,k;void init(){    int val;    memset(dp,0,sizeof(dp));    for(int i=0; i<n; i++)    {        val=0;        for(int j=i; j<n; j++)        {            val|=(1<<(s[j]-'a'));            dp[val]=max(dp[val],j-i+1);        }    }}int main(){    int T;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&k);        scanf("%s",s);        init();        for(int i=0; i<(1<<k); i++)            for(int j=0; j<k; j++)                if(i&(1<<j))        			dp[i]=max(dp[i],dp[i^(1<<j)]);        int ans=0;        for(int i=0; i<(1<<k); i++)            ans=max(dp[i]*dp[((1<<k)-1)^i],ans);        PRintf("%d/n",ans);    }    return 0;}