UVa 10453 Make Palindrome

一直都不太会做这种字符串的动规题，今天看了一份解题报告，才稍微有点明白。

感觉方法跟求最长公共子序列有点像……之前遇到过几个类似的，改天一块整理一下。

-------------------------------------------------------------------

题目：给定一个字符串，最少添加几个字符，能使它变成一个回文串。

递推公式：

dp[x][y]代表从第x个字符到y个字符中间最少需要添加几个字符。

if ( str[x] == str[y] ) dp[x][y] = dp[x+1][y-1];

else dp[x][y] = min( dp[x][y-1], dp[x+1][y] ) + 1;

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 const int MAXN = 1000 + 5;
  5 
  6 struct MAP
  7 {
  8     int cost;
  9     int path;
 10     int x, y;
 11 };
 12 
 13 char str[MAXN];
 14 char L[MAXN], R[MAXN];
 15 int left, right;
 16 MAP map[MAXN][MAXN];
 17 
 18 int DP( int x, int y )
 19 {
 20     if ( x >= y ) return 0;
 21     else if ( map[x][y].cost ) return map[x][y].cost;
 22     else
 23     {
 24         if ( str[x] == str[y] )
 25         {
 26             map[x][y].cost = DP( x + 1, y - 1 );
 27             map[x][y].path = 1;
 28             map[x][y].x = x + 1;
 29             map[x][y].y = y - 1;
 30         }
 31         else
 32         {
 33             int temp1 = DP( x, y - 1 ) + 1;
 34             int temp2 = DP( x + 1, y ) + 1;
 35             if ( temp1 < temp2 )
 36             {
 37                 map[x][y].cost = temp1;
 38                 map[x][y].path = 2;
 39                 map[x][y].x = x;
 40                 map[x][y].y = y - 1;
 41             }
 42             else
 43             {
 44                 map[x][y].cost = temp2;
 45                 map[x][y].path = 3;
 46                 map[x][y].x = x + 1;
 47                 map[x][y].y = y;
 48             }
 49         }
 50         return map[x][y].cost;
 51     }
 52 }
 53 
 54 bool OutputPath( int x, int y )
 55 {
 56     if ( x == y )
 57     {
 58         L[left++] = str[x];
 59         return true;
 60     }
 61     else
 62     {
 63         switch ( map[x][y].path )
 64         {
 65             case 1:
 66             L[ left++ ] = str[x];
 67             R[ right++ ] = str[x];
 68             if ( x == y - 1 ) return true;
 69             break;
 70 
 71             case 2:
 72             L[ left++ ] = str[y];
 73             R[ right++ ] = str[y];
 74             break;
 75 
 76             case 3:
 77             L[ left++ ] = str[x];
 78             R[ right++ ] = str[x];
 79             break;
 80         }
 81     }
 82     if ( OutputPath( map[x][y].x, map[x][y].y ) ) return true;
 83     return false;
 84 }
 85 
 86 void init( int len )
 87 {
 88     for ( int i = 0; i <= len; i++ )
 89       for ( int j = 0; j <= len; j++ )
 90           map[i][j].cost = 0;
 91     return;
 92 }
 93 
 94 int main()
 95 {
 96     while ( gets(str) != NULL )
 97     {
 98         int len = strlen(str);
 99         init( len );
100 
101         int ans = DP( 0, len - 1 );
102         printf("%d ", ans);
103 
104         left = right = 0;
105 
106         OutputPath( 0, len - 1 );
107         L[left] = '\0';
108         printf( "%s", L );
109 
110         for ( int i = right - 1; i >= 0; i-- )
111            putchar(R[i]);
112 
113         putchar('\n');
114     }
115     return 0;
116 }