UVA Make Palindrome(10453)

题目大意：

       给定一个字符串，用最少的插入操作的次数，使得该字符串变为回文。

 

解题思路：

      和UVA（10739） String to Palindrome一样，求出最少的操作次数，唯一不一样的就是这道题要将还原的回文输出出来。

      设置 dp[i][j] 表示第 i 个字符到第 j 个字符是回文时所需要操作的最少次数，字符串为 s ， 则状态转移方程为：

if( s[i] == s[j] )
     dp[i][j] = dp[i+1][j-1];
else
     dp[i][j] = min( dp[i+1][j], dp[i][j-1] ) + 1;

 输出dp[0][len]就是最少的操作次数；

        接下来就是如何输出回文字符串，方法就是利用dp[i][j]来递归输出。代码如下：

    if (i > j) return;
    if (i==j) { cout<<s[i]; return; }
    if (s[i] == s[j]) {
        cout<<s[i];   //先输出回文左边的字符
        output(i+1, j-1);    //不断递归直到输出回文中间的字符
        cout<<s[i];    //输出回文右边的字符
    } else if (dp[i][j] == dp[i+1][j] + 1) {
        cout<<s[i];
        output(i+1, j);
        cout<<s[i];
    } else {
        cout<<s[j];
        output(i, j-1);
        cout<<s[j];
    }

 

完整代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

char s[2010];
int dp[1010][1010];
int len;

void output( int i, int j )
{
    if (i > j) return;
    if (i==j) { cout<<s[i]; return; }
    if (s[i] == s[j]) {
        cout<<s[i];
        output(i+1, j-1);
        cout<<s[i];
    } else if (dp[i][j] == dp[i+1][j] + 1) {
        cout<<s[i];
        output(i+1, j);
        cout<<s[i];
    } else {
        cout<<s[j];
        output(i, j-1);
        cout<<s[j];
    }
}

int main()
{
	while( cin>>s )
	{
		memset( dp, 0, sizeof( dp ) );

		len = strlen( s );
		for( int i = len-2; i >= 0; i-- )
		{
			for( int j = i+1; j < len; j++ )
			{
				if( s[i] == s[j] )
					dp[i][j] = dp[i+1][j-1];
				else
				{
					dp[i][j] = min( dp[i+1][j], dp[i][j-1] ) + 1;
				}
			}
		}
		cout<<dp[0][len-1]<<" ";
		
		output( 0, len-1 );

		cout<<endl;
	}
	return 0;
}