1 /* 2     题意：给出一个长为n的仅由小写英文字母组成的字符串，求它的回文串划分的元素的最小个数，并按顺序输出此划分方案 3     回文串+回溯：dp[i] 表示前i+1个字符(从0开始)最少需要划分的数量，最大值是i+1，即单个回文串； 4         之前设置ok[j][j+i] 判断从j到j+i的字符是否为回文串(注意两个for的顺序，为满足ok[j][j+i] = ok[j+1][j+i-1]) 5         最后枚举找到最优划分点，用pre[i]记录前一个位置，print函数 输出空格 6 */ 7 #include 
     
       8 #include 
      
        9 #include 
       
        10 #include 
        
         11 #include 
         
          12 using namespace std;13 14 const int MAXN = 4e3 + 10;15 const int INF = 0x3f3f3f3f;16 int dp[MAXN];17 int pre[MAXN];18 bool ok[MAXN][MAXN];19 char s[MAXN];20 21 void print(int p)22 {23     if (pre[p] == -1)24     {25         for (int i=0; i<=p; ++i)    printf ("%c", s[i]);26     }27     else28     {29         print (pre[p]);    printf (" ");30         for (int i=pre[p]+1; i<=p; ++i)    printf ("%c", s[i]);31     }32 }33 34 void work(void)35 {36     int len = strlen (s);37 38     for (int i=0; i
          
           =0; --j)53 {54 if (ok[j+1][i])55 {56 if (dp[i] > dp[j] + 1)57 {58 dp[i] = dp[j] + 1; pre[i] = j;59 }60 }61 }62 }63 64 printf ("%d\n", dp[len-1]);65 print (len-1); puts ("");66 }67 68 int main(void) //URAL 1635 Mnemonics and Palindromes69 {70 //freopen ("P.in", "r", stdin);71 72 while (scanf ("%s", s) == 1)73 {74 memset (ok, false, sizeof (ok));75 memset (dp, 0, sizeof (dp));76 memset (pre, 0, sizeof (pre));77 78 work ();79 }80 81 return 0;82 }