hdu_5677_ztr loves substring(回文+二维多重背包)

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5677

题意：给你N个串，问能否选出小于K个回文字符串使得选出的字符串的长度之和为L。

题解：很容易想到求一下回文字符串的个数和长度，然后就背包处理一下，数据比较水，用了manacher和二进制背包加速，0ms过。

hdu_5677_ztr loves substring(回文+二维多重背包)

 #include<cstdio>

 #include<cstring>

 #define min(a,b) (a)>(b)?(b):(a)

 const int maxn = ;//字符串长度

 char s[];

 int bk[],t,n,k,l,val[],size[];

 bool dp[][];

 struct Manacher{

     char str[maxn<<];

     int p[maxn<<],len,mx,id,tl,ans,i;

     void maxlen(char *s){

         len=strlen(s),mx=,id=,tl=,str[tl++]='$',str[tl++]='#';

         for(i=;i<len;i++)str[tl++]=s[i],str[tl++]='#';

         for(i=,str[tl]=,ans=;i<tl;i++){

             p[i]=mx>i?min(p[(id<<)-i],mx-i):;

             while(str[i-p[i]]==str[i+p[i]])p[i]++;

             if(i+p[i]>mx)mx=i+p[i],id=i;

             if(str[i]=='#'&&p[i]==)continue;

                 bk[p[i]-]++;

         }

     }

 }M;

 void back(){

     int cnt=;//将所有的回文串二进制拆解

     for(int i=;i<=;i++){

         int tmp=;

         while(bk[i]>=tmp)

             val[++cnt]=tmp*i,size[cnt]=tmp,bk[i]-=tmp,tmp*=;

         if(bk[i])val[++cnt]=tmp*i,size[cnt]=tmp;

     }

     memset(dp,,sizeof(dp));

     dp[][]=;

     for(int i=;i<=cnt;i++){

         for(int j=k;j>=size[i];j--)

             for(int r=l;r>=val[i];r--)

             if(dp[j-size[i]][r-val[i]])dp[j][r]=;

     }

 }

 int main(){

     scanf("%d",&t);

     while(t--){

         scanf("%d%d%d",&n,&k,&l);

         memset(bk,,sizeof(bk));

         for(int i=;i<=n;i++){scanf("%s",s);M.maxlen(s);}

         back();

         if(dp[k][l])puts("True");

         else puts("False");

     }

     return ;

 }