题目链接
题目大意：给定一个由小写字母组成的字符串，删除其中0个或多个字符，使得剩下的字母（顺序不变）组成一个尽量长的回文串。如果有多解，输出字典序最小的解。
解题报告：dp[i][j]表示子串i~j变为回文串最少删除字母个数。
s[i]==s[j] dp[i][j]=dp[i+1][j-1]
dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1
再顺带求出字典序最小解。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int maxn=1010;int dp[maxn][maxn];
string path[maxn][maxn];
char ch[maxn];int main(){while( scanf("%s", ch+1 )==1 ){int n=strlen(ch+1);for ( int i=n; i>=1; i-- )for ( int j=i; j<=n; j++ ){if( ch[i]==ch[j] ){if( i==j ){dp[i][j]=0;path[i][j]=ch[i];}else{dp[i][j]=dp[i+1][j-1];path[i][j]=ch[i]+path[i+1][j-1]+ch[j];}}else {if( dp[i+1][j]>dp[i][j-1] ){dp[i][j]=dp[i][j-1]+1;path[i][j]=path[i][j-1];}else if( dp[i+1][j]<dp[i][j-1] ){dp[i][j]=dp[i+1][j]+1;path[i][j]=path[i+1][j];}else {dp[i][j]=dp[i+1][j]+1;path[i][j]=min(path[i+1][j], path[i][j-1]);}}}cout<<path[1][n]<<endl;}return 0;
}