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
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++