[UVA][dp] 10453 - Make Palindrome
Problem A
Make Palindrome
Input: standard input
Output: standard output
Time Limit: 8 seconds
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
abcdaaaa
abc
aab
abababaabababa
pqrsabcdpqrs
Sample Output
3 abcdcba0 aaaa
2 abcba
1 baab
0 abababaabababa
9 pqrsabcdpqrqpdcbasrqp
Author : Md. Kamruzzaman
The Real Programmers' Contest-2這動規其實還蠻有道理的，我要湊成 dp[i][j] 的最少迴文，假如
A[i] = A[j] 則直接由 dp[i+1][j-1] 的構成方法兩端都補上 A[i] 即可。
倘若A[i] != A[j] 由 dp[i+1][j] 的構成方法兩端都補上 A[i]。
反之 A[j] 的操作，取小的操作即可。
#include <stdio.h>
#include <string.h>
int dp[1005][1005];
char A[1005], argdp[1005][1005];
void print(int l, int r) {
if(l > r) return;
if(l == r) {
putchar(A[l]);
return;
}
if(argdp[l][r] == 1) {
putchar(A[l]);
print(l+1, r-1);
putchar(A[r]);
} else if(argdp[l][r] == 2) {
putchar(A[l]);
print(l+1, r);
putchar(A[l]);
} else {
putchar(A[r]);
print(l, r-1);
putchar(A[r]);
}
}
void sol(char *A) {
int i, j, Alen;
Alen = strlen(A);
for(i = 0; i < Alen; i++)
dp[i][i] = 0, dp[i+1][i] = 0;
for(i = 1; i <= Alen; i++) {
for(j = 0; j+i < Alen; j++) {
if(A[j] == A[j+i]) {
dp[j][j+i] = dp[j+1][j+i-1];
argdp[j][j+i] = 1;
} else {
if(dp[j+1][j+i] <= dp[j][j+i-1]) {
dp[j][j+i] = dp[j+1][j+i]+1;
argdp[j][j+i] = 2;
} else {
dp[j][j+i] = dp[j][j+i-1]+1;
argdp[j][j+i] = 3;
}
}
}
}
printf("%d ", dp[0][Alen-1]);
print(0, Alen-1);
puts("");
}
int main() {
while(gets(A))
sol(A);
return 0;
}