【HDOJ】1726 God’s cutter

简单DP。
 1 /* 1726 */
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 
 6 #define MAXN 105
 7 #define INF 99999
 8 
 9 bool isValid[MAXN][MAXN];
10 char s[MAXN];
11 int dp[MAXN];
12 
13 bool check(int l, int r) {
14     int i, j;
15 
16     for (i=l, j=r; i<=j; ++i, --j)
17         if (s[i] != s[j])
18             return false;
19     return true;
20 }
21 
22 int min(int a, int b) {
23     return a<b ? a:b;
24 }
25 
26 int main() {
27     int len;
28     int i, j, k;
29 
30     #ifndef ONLINE_JUDGE
31         freopen("data.in", "r", stdin);
32     #endif
33 
34     while (scanf("%s", s+1) != EOF) {
35         len = strlen(s+1);
36         memset(isValid, false, sizeof(isValid));
37         for (i=1; i<=len; ++i) {
38             isValid[i][i] = true;
39             for (j=i+1; j<=len; ++j)
40                 isValid[i][j] = check(i, j);
41         }
42 
43         dp[0] = -1;
44         for (i=1; i<=len; ++i) {
45             dp[i] = dp[i-1] + 1;
46             for (j=1; j<i; ++j) {
47                 if (isValid[j][i] && dp[j-1]+1<dp[i]) {
48                     dp[i] = dp[j-1] + 1;
49                 }
50             }
51         }
52         printf("%d
", dp[len]);
53     }
54 
55     return 0;
56 }