hdu 5677 ztr loves substring 多重背包

时间：2023-12-26 21:29:37

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 178    Accepted Submission(s): 93

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
Source

思路:二维费用的

#include <bits/stdc++.h>

using namespace std;

const int N = ;

const int INF = 0x3f3f3f3f;

int Ma[N << ], Mp[N << ];

char s[N];

int cnt[N];

void manacher(char s[], int len) {

    int l = ;

    Ma[l++] = '$';

    Ma[l++] = '#';

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

    {

        Ma[l++] = s[i];

        Ma[l++] = '#';

    }

    Ma[l] = ;

    int mx = , id = ;

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

    {

        Mp[i] = mx > i ? min(Mp[ * id - i], mx - i) : ;

        while(Ma[ i + Mp[i] ] == Ma[ i - Mp[i] ]) Mp[i]++;

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

    }

    for(int i = ; i < l; ++i) if(Mp[i] > ) {

        int p;

        if(Mp[i] & ) p = ; else p = ;

        for(int j = p; j < Mp[i]; j += ) cnt[j]++;

    }

}

int dp[N][N];

void Dp1(int v, int k, int l) {

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

    for(int j = ; j <= k; ++j)

    if(dp[i - v][j - ]) dp[i][j] = ;

}

void Dp2(int v, int num, int k, int l) {

    for(int i = l; i >= v; --i)

    for(int j = k; j >= num; --j)

    if(dp[i - v][j - num]) dp[i][j] = ;

}

void to(int x, int k, int l) {

    if(cnt[x] >= k && x * cnt[x] >= l) Dp1(x, k, l);

    else {

        int s = , tot = cnt[x];

        while(s < tot) {

            Dp2(x * s, s, k, l);

            tot -= s;

            s <<= ;

        }

        Dp2(tot * x, tot, k, l);

    }

}

bool solve(int k, int l) {

    memset(dp, , sizeof dp);

    dp[][] = ;

    for(int i = ; i <= ; ++i) if(cnt[i]) to(i, k, l);

    if(dp[l][k]) return true;

    return false;

}

int main() {

   // freopen("in", "r", stdin);

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

    while(_ --) {

        int n, k, l;

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

        memset(cnt, , sizeof cnt);

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

            scanf("%s", s);

            int len = strlen(s);

            manacher(s, len);

        }

        if(solve(k, l)) puts("True");

        else puts("False");

    }

    return ;

}

,且二维都要求恰好装满,那么初始化[0][0]能满足，其它状态都不满足

相关文章