UVa11404Palindromic Subsequence（最大回文串，區間DP）
Description
A Subsequence is a sequence obtained by deleting zero or more characters in a string. A Palindrome is a string which when read from left to right, reads same as when read from right to left. Given a string, find the longest palindromic
subsequence. If there are many answers to it, print the one that comes lexicographically earliest.
Constraints
- Maximum length of string is 1000.
- Each string has characters `a' to `z' only.
Input
Input consists of several strings, each in a separate line. Input is terminated by EOF.
Output
For each line in the input, print the output in a single line.
Sample Input
aabbaabb
computer
abzla
samhita
Sample Output
aabbaa
c
aba
aha
題意：
給定1個字符串s，對s進行刪除操作，使得剩下的子串是回文字符串，輸出最長的字符串，當有多個相同長度的就輸出字典序最小的。
思路：
由于要輸出字符串，所以在狀態轉移進程中要保存下字符串，用C++的string就方便很多，然后就是和找最長回文的方法1樣了。
定義結構體保存長度，和字符串，分別用len, s 表示
狀態的轉移方程為，如果頭尾相同，dp[i][j].len = dp[i + 1][j - 1].len + 2（長度加上首尾，所以增加2)；如果首尾不同，那末回文長度不增加 dp[i][j].len = max(dp[i + 1][j].len, dp[i][j - 1].len);
如果長度相同 dp[i + 1][j].len, == dp[i][j - 1].len，那末就要比較子串的字典序，取字典序小的，
也就是判斷 dp[i + 1][j].s, dp[i][j - 1].s。
<span style="font-size:18px;">#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const double PI = acos(⑴.0);
const double e = 2.718281828459;
const double eps = 1e⑻;
const int MAXN = 1010;
struct str
{
int len;
string s;
} dp[MAXN][MAXN];
char s[MAXN];
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(scanf("%s", s+1) != EOF)
{
int len = strlen(s+1);
for(int i = 1; i <= len; i++)
{ //初始化
dp[i][i].len = 1;
dp[i][i].s = s[i];
}
for(int k = 2; k <= len; k++) //控制區間大小
{
for(int i = 1, j = k; j <= len; i++, j++) //正推
//for(int i = len-k+1, j = len; i >= 1; i--, j--) //逆推
{
if(s[i] == s[j])
{
dp[i][j].len = dp[i+1][j⑴].len+2;
dp[i][j].s = s[i]+dp[i+1][j⑴].s+s[j];
}
else
{
if(dp[i][j⑴].len > dp[i+1][j].len ||
(dp[i][j⑴].len==dp[i+1][j].len&&dp[i][j⑴].s<dp[i+1][j].s))
{ //當 [i, j⑴] 的長度大于 [i+1, j] 的長度，或2者長度相等并且
//[i, j⑴] 的字典序小于 [i+1, j] 的字典序，則選擇 [i, j⑴]，否則選擇后者
dp[i][j].len = dp[i][j⑴].len;
dp[i][j].s = dp[i][j⑴].s;
}
else
{
dp[i][j].len = dp[i+1][j].len;
dp[i][j].s = dp[i+1][j].s;
}
}
}
}
cout<<dp[1][len].s<<endl;
}
return 0;
}
</span>
