区间DP UVA 10453 Make Palindrome-白红宇

区间DP UVA 10453 Make Palindrome

阅读量：4597 次

发布时间：2019-06-09

本文共 1576 字，大约阅读时间需要 5 分钟。

1 /* 2     题意：问最少插入多少个字符使得字符串变成回文串 3     区间DP：dp[i][j]表示[l, r]的字符串要成为回文需要插入几个字符串，那么dp[l][r] = dp[l+1][r-1]; (str[l] == str[r]) 4             dp[l][r] = min (dp[l+1][r], dp[l][r-1]) + 1，然后按照状态转移递归输出路径 5 */ 6 /************************************************ 7 * Author        :Running_Time 8 * Created Time  :2015-8-17 14:42:57 9 * File Name     :UVA_10453.cpp10  ************************************************/11 12 #include 
     
      13 #include 
      
       14 #include 
       
        15 #include 
        
         16 #include 
         
          17 #include 
          
           18 #include 
           
            19 #include 
            
             20 #include 
             
              21 #include 
              
               22 #include 
               
                23 #include 
                
                 24 #include 
                 25 #include 
                  
                   26 #include 
                   
                    27 #include 
                    
                     28 #include 
                     
                      29 using namespace std;30 31 #define lson l, mid, rt << 132 #define rson mid + 1, r, rt << 1 | 133 typedef long long ll;34 const int MAXN = 1e3 + 10;35 const int INF = 0x3f3f3f3f;36 const int MOD = 1e9 + 7;37 char str[MAXN];38 int dp[MAXN][MAXN];39 40 void print(int l, int r) {41 if (l > r) return ;42 if (l == r) printf ("%c", str[l]);43 else if (str[l] == str[r]) {44 printf ("%c", str[l]);45 print (l + 1, r - 1);46 printf ("%c", str[l]);47 }48 else if (dp[l][r] == dp[l+1][r] + 1) {49 printf ("%c", str[l]);50 print (l + 1, r);51 printf ("%c", str[l]);52 }53 else {54 printf ("%c", str[r]);55 print (l, r - 1);56 printf ("%c", str[r]);57 }58 }59 60 void work(void) {61 memset (dp, 0, sizeof (dp));62 int len = strlen (str);63 for (int i=2; i<=len; ++i) {64 for (int j=0; j+i-1