uva 10453 - Make Palindrome （區間dp，記憶化搜尋）

本文出自   http://blog.csdn.net/shuangde800

題目連結：  點選打開連結

題目大意

給一個字元串，要求添加最少個字元，把它變成回文串，并輸出。

思路

簡單的區間dp,

f(i, j) 表示區間(i, j) 内的字元串添加的最少個數，變成回文串

那麼, 如果str[i]==str[j], f(i, j) = f(i+1, j-1) + 1

f(i, j) = min{f(i+1, j), f(i, j-1)} + 1;

題目要輸出方案，那麼隻要再開一個數組,根據狀态轉移遞歸輸出即可

代碼

記憶化搜尋 + 遞推的區間dp都有實作

/**==========================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source：uva-10453 Make Palindrome
 *   @type: 記憶化搜尋， 區間dp
 *   @author: shuangde
 *   @blog: blog.csdn.net/shuangde800
 *   @email: [email protected]
 *===========================================*/

#include
   
    
#include
    
     
#include
     
      
#include
      
       
#include
       
         #include
        
          #include
         
           using namespace std; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 1010; char str[MAXN]; int len; int f[MAXN][MAXN]; // 記憶化搜尋版本, f數組初始化INF int dfs(int i, int j) { if (i>j || i==j) return f[i][j] = 0; if (f[i][j] != INF) return f[i][j]; int& ans = f[i][j]; if (str[i] == str[j]) ans = dfs(i+1, j-1); ans = min(ans, min(dfs(i+1, j), dfs(i, j-1))+1); return f[i][j]; } // 遞推區間dp void dp() { memset(f, 0, sizeof(f)); for (int d = 2; d <= len; ++d) for (int l = 0; l+d-1 <= len; ++l) { int r = l + d - 1; int& ans = f[l][r] = INF; if(str[l] == str[r]) ans = f[l+1][r-1]; ans = min(ans, min(f[l+1][r], f[l][r-1])+1); } } void output(int i, int j) { if (i > j) return; if (i==j) { printf("%c", str[i]); return; } if (str[i] == str[j]) { printf("%c", str[i]); output(i+1, j-1); printf("%c", str[i]); } else if (f[i][j] == f[i+1][j] + 1) { printf("%c", str[i]); output(i+1, j); printf("%c", str[i]); } else { printf("%c", str[j]); output(i, j-1); printf("%c", str[j]); } } int main(){ while (gets(str)) { len = strlen(str); dp(); printf("%d ", f[0][len-1]); output(0, len-1); putchar('\n'); } return 0; }