ztr loves substring

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

ztr love reserach substring.Today ,he has n string.Now ztr want to konw,can he take out exactly k palindrome from all substring of these n string,and thrn sum of length of these k substring is L.for example string "yjqqaq".this string contains plalindromes:"y","j","q","a","q","qq","qaq".so we can choose "qq" and "qaq".

Input

The first line of input contains an positive integer T(T<=10) indicating the number of test cases.
For each test case:
First line contains these positive integer N(1<=N<=100),K(1<=K<=100),L(L<=100).
The next N line,each line contains a string only contains lowercase.Guarantee even length of string won't more than L.

Output

For each test,Output a line.If can output "True",else output "False".

Sample Input

2 3 7

yjqqaq

claris

2 2 7

popoqqq

fwwf

1 3 3

aaa

Sample Output

False

True

题解：

（多重背包都快不会打了我已经完蛋了）

这道题相对来说还是比较裸的。先用manacher计算出每种长度回文串出现的个数。

在将长度视为物品跑一个多重背包即可。

关于这里的背包，我们可以设f[i][j]为一个bool滚动数组，表示构造长度为i的串用了j个子串能不能成立。

那么显然3层循环即可。我打的是二进制分解然后01背包（其实是因为单调队列不会）

代码见下：

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int N=;

 int n,t,m,k,ct,mx,l;

 int r[N<<],f[N][N],vis[N];

 char s[N<<],str[N];

 inline int max(int a,int b){return a>b?a:b;}

 inline int min(int a,int b){return a<b?a:b;}

 inline void manacher()

 {

     memset(s,,sizeof(s));

     n=;m=strlen(str);

     s[n++]=;s[n++]=;

     for(int i=;i<m;i++)s[n++]=str[i],s[n++]=;

     memset(r,,sizeof(r));ct=mx=;

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

     {

         if(i<mx)r[i]=min(mx-i,r[*ct-i]);

         else r[i]=;

         while(<=i-r[i]&&i+r[i]<n&&s[i-r[i]]==s[i+r[i]])r[i]++;

         if(i+r[i]>mx)ct=i,mx=i+r[i];

         int j=r[i]-;

         while(j>=)vis[j]++,j-=;

     }

 }

 int c[N*N],v[N*N],cnt;

 inline bool backpack()

 {

     memset(f,,sizeof(f));

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

     {

         int tmp=;

         while(vis[i]>=tmp)

             c[++cnt]=tmp*i,v[cnt]=tmp,vis[i]-=tmp,tmp<<=;

         if(vis[i])

             c[++cnt]=vis[i]*i,v[cnt]=vis[i];

     }

     f[][]=;

     for(int u=;u<=cnt;u++)

         for(int i=l;i>=c[u];i--)

             for(int j=k;j>=v[u];j--)

                 f[i][j]|=f[i-c[u]][j-v[u]];

     return f[l][k];

 }

 int main()

 {

     int cnt;scanf("%d",&cnt);

     while(cnt--)

     {

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

         memset(vis,,sizeof(vis));

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

             scanf("%s",str),manacher();

         if(backpack())printf("True\n");

         else printf("False\n");

     }

 }

HDU5677

秒客网

[HDU5677]ztr loves substring

ztr loves substring

相关文章