HDU 5677 ztr loves substring（Manacher+dp+二进制分解）

时间：2023-07-05 20:50:02

题目链接：HDU 5677 ztr loves substring

题意：有n个字符串，任选k个回文子串，问其长度之和能否等于L。

题解：用manacher算法求出所有回文子串的长度，并记录各长度回文子串的个数，再用背包思想判断是否有解。

dp[i][j]：选取i个回文子串，长度之和是否为j

其中用到二进制分解思想，将回文串长为i的数量cnt[i]拆成1+2+4+8+…形式，进行优化。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 #define CLR(a,b) memset((a),(b),sizeof((a)))

 const int N = ;

 int dp[N][N], w[N*N*N], cnt[N], cnt1[N*N*N];

 char s[N*];

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

     char Ma[N*];

     int Mp[N*] , l = ;

     CLR(Mp, );

     Ma[l++] = '$';  Ma[l++] = '#';

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

         Ma[l++] = s[i];  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) {

             id = i;

             mx = i + Mp[i];

         }

         if(Ma[i] == '#'&& Mp[i] == ) continue;

         cnt[Mp[i]-]++;//记录该回文串长度数量

     }

 }

 int main(){

     int t, i, j, n, k, l, x, num;

     scanf("%d", &t);

     while(t--) {

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

         CLR(dp, ); CLR(cnt, );

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

             scanf("%s", s);

             int len = strlen(s);

             Manacher(s, len);

         }

         num = ;

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

             for(j = ; j <= cnt[i]; cnt[i] -= j, j <<= ) {

                 w[num] = j * i;

                 cnt1[num++] = j;

             }

             if(cnt[i]) { w[num] = j * i; cnt1[num++] = j; }

         }

         dp[][] = ;

         for(i = ; i < num; ++i)

             for(j = l; j >= w[i]; --j)

                 for(x = cnt1[i]; x <= k; ++x)

                     dp[x][j] |= dp[x-cnt1[i]][j-w[i]];

         if(dp[k][l]) puts("True");

         else puts("False");

     }

     return ;

 }

0ms

相关文章