FZU 2218【状压】

题意：

给出长为n的字符串，含有前k种小写字母，求两个不含重复元素的连续子串，使得他们的长度乘积最大。

思路：

字符种类16 ->(套路) 状压

暴力2000*2000得所有连续子串的长度，得每个状态的最优；

dp使得包含字符个数最优。

利用异或取反得最大值。

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

}

巴特西

FZU 2218【状压】

最新文章

热门文章