UVA - 10453 Make Palindrome

本文主要是介绍UVA - 10453 Make Palindrome，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：跟之前删除，添加，替换转化成回文串一个意思，还是从后往前枚举，最后根据dp[i+1][j]，dp[i][j-1]的大小，我们就可以判断是添加在哪一边了，如果dp[i+1][j]大的话，那么果断是复制s[l]在最右边，因为不相等的话我们肯定要添加一个，当然要找最小的啦，另一种情况就复制s[r]在最左边，打印的时候注意如果有中间的字符的时候要记得打印就行了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1010;int dp[MAXN][MAXN];
string s;void print(int l,int r){if (l > r)return;if (l == r){cout << s[l];return;}  if (s[l] == s[r]){cout << s[l];print(l+1,r-1);cout << s[r];}else {if (dp[l+1][r] < dp[l][r-1]){cout << s[l];print(l+1,r);cout << s[l];}else {cout << s[r];print(l,r-1);cout << s[r];}}
}int main(){while (cin >> s){int len = s.length();memset(dp,0,sizeof(dp));for (int i = len - 1; 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;printf("%d ",dp[0][len-1]);print(0,len-1);printf("\n");}return 0;
}

这篇关于UVA - 10453 Make Palindrome的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---