URAL 1635. Mnemonics and Palindromes(DP)

本来用区间DP，3次方的复杂度，T了，看了看题解，降维，直接二次方的复杂度可以解。然后折腾一下输出路径。。终于过了。
 1 #include <cstring>
 2 #include <cstdio>
 3 #include <string>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <cmath>
 7 using namespace std;
 8 char str[4001];
 9 int dp[4001][4001];
10 int p[4001];
11 int pre[4001];
12 int flag[4001];
13 int main()
14 {
15     int i,len,j;
16     scanf("%s",str);
17     len = strlen(str);
18     for(i = 0; i <= len; i ++)
19     {
20         dp[i][i] = 1;
21         for(j = 1;; j ++)
22         {
23             if(i-j+1 < 0)break;
24             if(i+j >= len) break;
25             if(str[i-j] != str[i+j]) break;
26             dp[i-j][i+j] = 1;
27         }
28         for(j = 1;; j ++)
29         {
30             if(i-j+1 < 0)break;
31             if(i+j >= len) break;
32             if(str[i-j+1] != str[i+j]) break;
33             dp[i-j+1][i+j] = 1;
34         }
35     }
36     for(i = 0; i < len; i ++)
37         p[i] = 100000000;
38     p[0] = 1;
39     for(i = 1; i < len; i ++)
40     {
41         if(dp[0][i])
42         {
43             pre[i] = 0;
44             p[i] = 1;
45         }
46     }
47     for(i = 0; i < len; i ++)
48     {
49         if(p[i] == 1) continue;
50         for(j = 0; j < i; j ++)
51         {
52             if(dp[j+1][i])
53             {
54                 if(p[i] > p[j] + 1)
55                 {
56                     pre[i] = j+1;
57                     p[i] = p[j]+1;
58                 }
59             }
60         }
61     }
62     printf("%d
",p[len-1]);
63     int a = pre[len-1];
64     if(a != 0)
65     flag[a] = 1;
66     a --;
67     while(p[len-1] >= 2)
68     {
69         a = pre[a];
70         if(a != 0)
71         flag[a] = 1;
72         a --;
73         p[len-1] --;
74     }
75     for(i = 0; i < len; i ++)
76     {
77         if(flag[i]) printf(" ");
78         printf("%c",str[i]);
79     }
80     printf("
");
81     return 0;
82 }