HDU 5667

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

3
2 3 7
yjqqaq
claris
2 2 7
popoqqq
fwwf
1 3 3
aaa

 

Sample Output

False
True
True

样例很有趣对不对

这题是用Manacher或回文自动机求出所有的回文串的长和数量

然后就转化成了bool DP多重背包

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int T,n,k,l;
char s[105];
int len[105],ch[105][26],num[105],fail[105],tot,num_len[105];
int val[105*105],c[105*105],cnt;
bool f[105][105];


void clear(){
    tot=0;
    memset(ch,0,sizeof ch);
    memset(num,0,sizeof num);
    memset(fail,0,sizeof fail);
    memset(len,0,sizeof len);
}

inline int get_fail(int x,int le){
    while(s[le-len[x]-1]!=s[le])x=fail[x];
    return x;
}

inline int newnode(int x){
    len[tot]=x;
    return tot++;
}

void build(char *s){
    newnode(0);newnode(-1);
    fail[0]=1;s[0]=-1;
    int last=0,Ans=0;
    for(int i=1;s[i];i++){
        s[i]-='a';
        int rt=get_fail(last,i);
        if(ch[rt][s[i]]==0){
            int now = newnode(len[rt]+2);
            Ans = max(Ans,len[now]);
            fail[now]=ch[get_fail(fail[rt],i)][s[i]];
            ch[rt][s[i]]=now;
        }
        num[last=ch[rt][s[i]]]++;
    }
}

bool Dp(){
    memset(f,0,sizeof f);
    cnt=0;
    for(int i=1;i<=100;i++){
        int tmp=1;
        while(num_len[i]>=tmp){
            val[++cnt]=i*tmp;
            c[cnt]=tmp;
            num_len[i]-=tmp;
            tmp*=2;
        }
        if(num_len[i]){
            val[++cnt]=num_len[i]*i;
            c[cnt]=num_len[i];
        }
    }  
    f[0][0]=1;
    for(int i=1;i<=cnt;i++)
        for(int j=l;j>=val[i];j--)
            for(int o=c[i];o<=k;o++)
                f[j][o]|=f[j-val[i]][o-c[i]];
    return f[l][k];
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&k,&l);
        memset(num_len,0,sizeof num_len);
        for(int i=1;i<=n;i++){
            scanf("%s",s+1);
            clear();build(s);
            for(int j=tot;j>=0;j--){
                num[fail[j]]+=num[j];
                num_len[len[j]]+=num[j];
            }
        }
        if(Dp())printf("True
");
        else printf("False
");
    }
}