LOJ2484 CEOI2017 Palindromic Partitions DP、回文树

当我打开Luogu题解发现这道题可以Hash+贪心的时候我的内心是崩溃的……

但是看到这道题不都应该认为这是一道PAM的练手好题么……

首先把原字符串重排为\(s_1s_ks_2s_{k-1}s_3s_{k-2}...\)之后，我们不难发现：在一种对原串的回文划分中，对应的一对字符串在新的字符串上对应了一个长度为偶数的回文串。

那么设\(dp_i\)表示将新字符串的长度为\(i\)的前缀划分为若干个长度为偶数的回文串，最多划分多少份。在回文树上可以进行转移。使用“一个长度为\(n\)串的回文后缀形成\(log n\)个等差数列”的结论将DP优化为\(O(nlogn)\)的复杂度。具体步骤可以看yyb的CF932G Palindrome Partition的题解

最后我们取\(\max(dp_i + [i < L](2 \mid i))\)作为答案。

注意悠着点开数组……

#include<bits/stdc++.h>

//this code is written by Itst

using namespace std;

const int _ = 1e6 + 7;

char s[_] , tmp[_]; int dp[_] , pre[_] , T , L;

namespace PAM{

    int trans[_][26] , fa[_] , len[_] , diff[_] , anc[_];

    int cnt , lst;

#define clr(x) memset(x , 0 , sizeof(x[0]) * (cnt + 1))

    void init(){

        clr(trans); clr(fa); clr(len); clr(diff); clr(anc);

        lst = 0; cnt = 1; len[1] = -1; fa[0] = fa[1] = 1;

    }

    void extend(int x){

        int p = lst;

        while(s[x - len[p] - 1] != s[x]) p = fa[p];

        if(trans[p][s[x] - 'a'])

            return (void)(lst = trans[p][s[x] - 'a']);

        int k = ++cnt , q = fa[p];

        while(s[x - len[q] - 1] != s[x]) q = fa[q];

        fa[k] = trans[q][s[x] - 'a']; trans[p][s[x] - 'a'] = k;

        len[k] = len[p] + 2; lst = k;

        diff[k] = len[k] - len[fa[k]]; anc[k] = diff[k] == diff[fa[k]] ? anc[fa[k]] : k;

    }

}

using namespace PAM;

int main(){

#ifndef ONLINE_JUDGE

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

    //freopen("out","w",stdout);

#endif

    for(scanf("%d" , &T) ; T ; --T){

        memset(dp , -0x3f , sizeof(dp)); dp[0] = 0;

        memset(pre , -0x3f , sizeof(pre));

        scanf("%s" , tmp + 1); L = strlen(tmp + 1);

        int cnt = 0;

        for(int i = 1 , j = L ; i <= j ; (i + j - L) & 1 ? ++i : --j)

            s[++cnt] = (i + j - L) & 1 ? tmp[i] : tmp[j];

        init();

        for(int i = 1 ; i <= L ; ++i){

            extend(i);

            for(int t = lst ; t ; t = fa[anc[t]]){

                if(anc[t] != t)

                    pre[t] = max(pre[fa[t]] , dp[i - len[anc[t]]]);

                else pre[t] = dp[i - len[anc[t]]];

                if(!(i & 1))

                    dp[i] = max(dp[i] , pre[t]);

            }

            dp[i] += 2;

        }

        int MAX = 0;

        for(int i = 0 ; i <= L ; i += 2)

            MAX = max(MAX , dp[i] + (i < L));

        cout << MAX << endl;

    }

    return 0;

}

巴特西

LOJ2484 CEOI2017 Palindromic Partitions DP、回文树

最新文章

热门文章