URAL1635. Mnemonics and Palindromes（DP）

先初始化一下所有的回文串再O（n*n)DP
输出路径dfs 刚开始存所有回文 ME了后来发现用不着改了改了OK了数据还挺强
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 using namespace std;
  7 #define N 4010
  8 #define INF 0xfffffff
  9 int dp[N];
 10 char s[4010];
 11 int path[2][4010],o[4010],q[4010][4010],k;
 12 int g,flag,pp[2];
 13 void init()
 14 {
 15     int i,j;
 16     k = strlen(s);
 17     for(i =0 ; i < k ; i++)
 18     {
 19         int tt=0;
 20         while(i-tt>=0&&i+tt<k&&s[i-tt]==s[i+tt])
 21         {
 22 
 23             g++;
 24             int x1 = i-tt,x2 = i+tt;
 25             o[x2]++;
 26             q[x2][o[x2]] = x1;
 27             tt++;
 28         }
 29         tt = 1;
 30         while(i-tt+1>=0&&i+tt<k&&s[i-tt+1]==s[i+tt])
 31         {
 32             g++;
 33             int x1 = i-tt+1,x2 = i+tt;
 34             o[x2]++;
 35             q[x2][o[x2]] = x1;
 36             tt++;
 37         }
 38     }
 39 }
 40 void dfs(int u,int d,int v)
 41 {
 42     if(flag) return ;
 43     path[0][v] = u;
 44     path[1][v] = d;
 45     int i,j;
 46     if(v==dp[k-1])
 47     {
 48         for(i = dp[k-1]; i > 1 ; i--)
 49         {
 50             for(j = path[0][i]; j <= path[1][i]; j++)
 51             printf("%c",s[j]);
 52             printf(" ");
 53         }
 54         for(j = path[0][1]; j <= path[1][1]; j++)
 55             printf("%c",s[j]);
 56         puts("");
 57         flag = 1;
 58         return ;
 59     }
 60     for(i = 1 ; i <= o[u-1] ; i++)
 61     {
 62         if(q[u-1][i]==0)
 63         dfs(q[u-1][i],u-1,v+1);
 64         else
 65         if(dp[u-1]==dp[q[u-1][i]-1]+1)
 66         {
 67             dfs(q[u-1][i],u-1,v+1);
 68         }
 69     }
 70 }
 71 int main()
 72 {
 73     int i,j;
 74     scanf("%s",s);
 75     init();
 76     for(i = 1 ; i <= k ; i++)
 77     dp[i] = INF;
 78     dp[0] = 0;
 79     for(i = 0; i < k ;i++)
 80     {
 81         if(o[i])
 82         {
 83             for(j = 1;j <= o[i] ; j++)
 84             {
 85                 if(q[i][j]==0)
 86                 {
 87                     dp[i] = 1;
 88                     pp[1] = i;
 89                     pp[0] = q[i][j];
 90                 }
 91                 else if(dp[i]>dp[q[i][j]-1]+1)
 92                 {
 93                      dp[i] = dp[q[i][j]-1]+1;
 94                      pp[0] = q[i][j];
 95                      pp[1] = i;
 96                 }
 97             }
 98         }
 99     }
100     printf("%d
",dp[k-1]);
101     dfs(pp[0],pp[1],1);
102     return 0;
103 }
View Code