首页 > ACM题库 > UVA > UVA-10453-Make Palindrome[区间dp]
2014
01-20

UVA-10453-Make Palindrome[区间dp]

Make Palindrome

By definition palindrome is a string which is not changed when reversed. “MADAM” is a nice example of palindrome. It is an easy job to test whether a given string is a palindrome or not. But it may not be so easy to generate a palindrome.

Here we will make a palindrome generator which will take an input string and return a palindrome. You can easily verify that for a string of length ‘n’, no more than (n-1) characters are required to make it a palindrome. Consider “abcd” and its palindrome “abcdcba” or “abc” and its palindrome “abcba”. But life is not so easy for programmers!! We always want optimal cost. And you have to find the minimum number of characters required to make a given string to a palindrome if you are allowed to insert characters at any position of the string.

Input

Each input line consists only of lower case letters. The size of input string will be at most 1000. Input is terminated by EOF.

Output

For each input print the minimum number of characters and such a palindrome seperated by one space in a line. There may be many such palindromes. Any one will be accepted.

Sample Input

abcd aaaa abc aab abababaabababa pqrsabcdpqrs

Sample Output

3 abcdcba 0 aaaa 2 abcba 1 baab 0 abababaabababa 9 pqrsabcdpqrqpdcbasrqp

题目大意

给一个字符串,要求添加最少个字符,把它变成回文串,并输出。

思路

简单的区间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: zengshuangde@gmail.com
 *===========================================*/

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
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;
}