UVa 11584 划分成回文串

题意：

给出一串字符，把它划分成尽量少的回文串。

思路：

用d[i]表示划分到i时所能划分的最小个数，转移方程为d[i]=min{d[i],d[j]+1},当然前提是j+1~i是回文串，我们可以预处理计算出所有的回文串，这样转移时就比较方便。

 1 #include<iostream> 
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<string>
 5 using namespace std;
 6 
 7 const int maxn = 1000 + 10;
 8 
 9 int ans[maxn][maxn];
10 char a[maxn];
11 int d[maxn];
12 
13 int main()
14 {
15     //freopen("D:\txt.txt", "r", stdin);
16     int t;
17     cin >> t;
18     while (t--)
19     {
20         memset(ans, 0, sizeof(ans));
21         memset(d, 0, sizeof(d));
22         cin >> a+1;
23         int l = strlen(a+1);
24 
25         //打表，判断i~j是否是回文串
26         for (int i = 1; i <= l; i++)
27         {
28             for (int j = i; j <= l; j++)
29             {
30                 int left = i, right = j;
31                 int ok = 1;
32                 while (left <= right)
33                 {
34                     if (a[left] != a[right])
35                     {
36                         ok = 0;
37                         break;
38                     }
39                     left++;
40                     right--;
41                 }
42                 if (ok)  ans[i][j] = 1;
43             }
44         }
45 
46         d[0] = 0;
47         for (int i = 1; i <= l; i++)
48         {
49             d[i] = d[i-1]+1;     
50             for (int j = 1; j <= i; j++)
51             {
52                 if (ans[j][i])    
53                 d[i] = min(d[i], d[j-1] + 1);
54             }
55         }
56         cout << d[l] << endl;
57     }
58     return 0;
59 }