HDU 5677 ztr loves substring（回文串加多重背包）
HDU 5677 ztr loves substring（回文串加多重背包）
ztr loves substring
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 219 Accepted Submission(s): 119
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 indicating the number of test cases. For each test case: First line contains these positive integer . 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
aaaSample Output
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;
}