题意: 输入一个由小写字母组成的字符串(长度不超过1000),你的任务是把它划分成尽量少的回文串。
例如,racecar本身就是回文串;fastcar只能分成7个单字母的回文串,aaadbccb最少分成3个回文串:aaa, d, bccb。
分析: 设d为字符0~i划分成的最小回文串的个数,则d = min{d[j] + 1 | s[j+1~i]是回文串}。
可以先用O(n*n)时间预处理s[i..j]是否为回文串。方法是枚举中心,然后不断向左右延伸,直到左右字符不同为止。
代码: 1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5
6 const int UP = 1000 + 5;
7 int d[UP]; // d为前i个字符划分成的最小回文串个数
8 char s[UP];
9 bool isp[UP][UP]; // isp[j]标记s[i..j]是否为回文串
10
11 void init(char* s, int len){
12 memset(isp, false, sizeof(isp));
13 for(int t = 1; t <= len; t++){
14 for(int f = t, b = t; 1 <= f && b <= len; f--, b++){
15 if(s[f] == s) isp[f] = true;
16 else break;
17 }
18 for(int f = t, b = t + 1; 1 <= f && b <= len; f--, b++){
19 if(s[f] == s) isp[f] = true;
20 else break;
21 }
22 }
23 }
24
25 int main(){
26 int T, len;
27 scanf("%d", &T);
28 while(T--){
29 scanf("%s", s + 1);
30 init(s, len = strlen(s + 1));
31 for(int t = 1; t <= len; t++){
32 d[t] = t;
33 for(int i = 1; i <= t; i++)
34 if(isp[t]) d[t] = min(d[t], d[i-1] + 1);
35 }
36 printf("%d\n", d[len]);
37 }
38 return 0;
39 }
|