回文切割

Problem’s Website

  • 切割回文

    Solution

  • 区间dp,我们设f[i]为到第i位需要切割的次数,答案为f[strlen(ss)],我们需要预处理一下,对于判断回文串,最好的方法就是马拉车算法,不懂得可以见我的另一篇题解马拉车算法, 我们首先枚举右端点i,在枚举左端点j,判断一下j-i是否为回文串,如果是,则进行转移,但要注意,我们这样转移会使方案数多1所以最后要-1。

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define gc getchar()
    using namespace std;
    int sc() {
    int xx = 0, ff = 1; char cch = gc;
    while(cch < '0' || cch > '9') {
    if(cch == '-') ff = -1; cch = gc;
    }
    while(cch >= '0' && cch <= '9') {
    xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    }
    return xx * ff;
    }
    int t, len = 1, mid, r;
    int p[1010 << 1], f[1010 << 1];
    char ss[1010], s[1010 << 1];
    bool check(int ll, int rr) {
    if((((p[ll + rr] << 1) - 1) >> 1) >= rr - ll + 1) return true;
    return false;
    }
    int main() {
    t = sc();
    while(t--) {
    len = 1;
    mid = r = 0;
    memset(f, 0x7f, sizeof(f));
    memset(p, 0, sizeof(p));
    f[0] = 0;
    scanf("%s", ss + 1);
    s[0] = '|'; s[1] = '|';
    for(int i = 1; i <= strlen(ss + 1); i++) {
    s[++len] = ss[i];
    s[++len] = '|';
    }
    for(int i = 1; i <= len; i++) {
    if(i < r)
    p[i] = min(r - i, p[(mid << 1) - i]);
    else
    p[i] = 1;
    while(s[i + p[i]] == s[i - p[i]])
    p[i]++;
    if(p[i] + i > r)
    r = p[i] + i, mid = i;
    }
    // cout << len << endl;
    // for(int i = 1; i <= len; i++)
    // cout << p[i] << " ";
    for(int i = 1; i <= strlen(ss + 1); i++)
    for(int j = 1; j <= i; j++)
    if(check(j, i))
    f[i] = min(f[i], f[j - 1] + 1);
    printf("%d\n", f[strlen(ss + 1)] - 1);
    }
    return 0;
    }

rp++