这一定是 ljt 写过的最短的题解。

先上一个部分分：朴实无华的区间 dp $\text{45pts}$

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
#include <cstdio>
#include <cstring>

const int maxn = (int) 1e3 + 5;

int T, n, dp[maxn][maxn];
char s[maxn];

inline bool f(int l, int r, int k) {
    for(int i = 0; i < k; i++) {
        if(s[l + i] != s[r + i])
            return false;
    }
    return true;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        for(int i = 1; i <= n; i++)
            dp[i][i] = 1;
        for(int len = 2; len <= n; len++) {
            for(int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                bool flag = 0;
                for(int k = 1; k <= len / 2; k++) {
                    if(f(i, j - k + 1, k)) {
                        flag = 1;
                        dp[i][j] = dp[i + k][j - k] + 2;
                        break;
                    }
                }
                if(!flag)
                    dp[i][j] = 1;
            }
        }
        printf("%d\n", dp[1][n]);
    }
    return 0;
}

如上的代码，内存不够，时间也要超限，那我们需要找新的办法。

正解：贪心 + Hash

因为要划分为尽量多的部分，所以我们从两边开始找，设两个指针分别指着从左往右数和从右往左数第 $i$ 个字符。只要找到两个字符串一样，就把它们分离出来。

两个字符串是否一样可以通过 Hash 判断，但是有个问题：我们是从两边往中间枚举的，右边那个字符串是倒着枚举的，怎么判断呢？

这个很简单，我们只需要判断一下当前右边遍历到的字符是字符串的第几个，假设它是第 $k$ 个，那么就加上它乘以 $base^k$ 即可。

最后有个细节：如果字符串的长度是奇数，或者还剩下一些字符，那么需要把这些字符作为一个区间，答案要加一。

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
#include <cstdio>
#include <cstring>
#define ull unsigned long long

const int maxn = (int) 1e6 + 5, p = 97, base = 10;

int T, n;
char s[maxn];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        ull hash1 = 0ull, hash2 = 0ull, pow = 1;
        int ans = 0;
        for(int i = 1; i <= n / 2; i++) {
            hash1 = hash1 * p + s[i];
            hash2 = hash2 + s[n - i + 1] * pow;
            pow *= p;
            if(hash1 == hash2) {
                ans += 2;
                hash1 = hash2 = 0ull;
                pow = 1;
            }
        }
        if((n & 1) || hash1)
            ++ans;
        printf("%d\n", ans);
    }
    return 0;
}