本文主要是介绍uva 11404 - Palindromic Subsequence(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 11404 - Palindromic Subsequence
题目大意：给出一个字符串，要求删除某些字符，使得字符串变成回文串，要求回文串尽量长，且字典序最小。
解题思路：dp，dp[i][j].val表示说从i~j的最大回文串长度，d[i][j].ans表示最优解。
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>using namespace std;
const int N = 1005;
struct state {string ans;int val;bool operator >(const state& a) {if (this->val != a.val) return this->val > a.val;return this->ans < a.ans;}
} dp[N][N];char str[N];int main () {while (scanf("%s", str+1) == 1) {int n = strlen(str+1);for (int i = n; i >= 1; i--) {dp[i][i].val = 1;dp[i][i].ans = str[i];for (int j = i+1; j <= n; j++) {if (str[i] == str[j]) {dp[i][j].val = dp[i+1][j-1].val + 2;dp[i][j].ans = str[i] + dp[i+1][j-1].ans + str[j];} else {if (dp[i+1][j] > dp[i][j-1]) {dp[i][j].val = dp[i+1][j].val;dp[i][j].ans = dp[i+1][j].ans;} else {dp[i][j].val = dp[i][j-1].val;dp[i][j].ans = dp[i][j-1].ans;}}}}cout << dp[1][n].ans << endl;}return 0;
}
这篇关于uva 11404 - Palindromic Subsequence(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
