HDU 5677 ztr loves substring（回文串加多重背包）

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

False
True
True
由于字符串的长度只有100，所以我们可以用暴力求所有的回文子串，可以动态规划去求。然后就可以用多重二维费用背包来处理，这里不需要用单调队列优化，不会超时，另外如果K>L直接是False
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;
int dp[105][105];
int bp[105][105];
int v[105];
int c[105];
char a[105];
int n,K,L;
void OneZeroPack(int v,int w)
{
    for(int i=K;i>=1;i--)
    {
        for(int j=L;j>=v;j--)
        {
            bp[i][j]=max(bp[i][j],bp[i-1][j-v]+w);
        }
    }
}
void CompletePack(int v,int w)
{
    for(int i=1;i<=K;i++)
    {
        for(int j=v;j<=L;j++)
        {
            bp[i][j]=max(bp[i][j],bp[i-1][j-v]+w);
        }
    }
}
void MulitplyPack(int v,int w,int c)
{
    if(c*w>=L)
    {
        CompletePack(v,w);
        return;
    }
    int k=1;
    while(k<c)
    {
       OneZeroPack(k*v,k*w);
        c-=k;
        k<<=1;
    }
    OneZeroPack(c*v,c*w);
}
int main()
{
    int t;
    scanf("%d",&t);
    int m;
    while(t--)
    {
        scanf("%d%d%d",&n,&K,&L);
        m=0;
       
        memset(c,0,sizeof(c));
        memset(v,0,sizeof(v));
        v[0]=1;
        for(int i=1;i<=n;i++)
        {
            memset(dp,0,sizeof(dp));
            for(int p=1;p<=100;p++)
                dp[p][p]=1;
            scanf("%s",a);
            int len=strlen(a);
            m=max(m,len);
            c[0]+=len;
            for(int l=1;l<=len-1;l++)
            {
                int num=0;
                for(int i=0;i+l<=len-1;i++)
                {
                    int j=i+l;
                    if(a[i]==a[j]&&(j-i==1||dp[i+1][j-1]==1))
                    {
                        dp[i][j]=1;
                        num++;
                    }
                }
                v[l]=l+1;
                c[l]+=num;
            }
        }
        memset(bp,0,sizeof(bp));
        for(int i=0;i<m;i++)
        {
            if(c[i]==0) continue;
            MulitplyPack(v[i],v[i],c[i]);
        }
        if(K>L)
        {
            printf("False\n");
            continue;
        }
        if(bp[K][L]==L)
            printf("True\n");
        else
            printf("False\n");

    }
    return 0;
}