题目大意
给定一个长度不超过5*10^4的只包含小写字母的字符串,要求你求它的回文子序列,如果存在长度为100的回文子序列,那么只要输出长度为一百的回文子序列即可,否则输出它的最长回文子序列
题解
这个题很考验思维~~~相当不错的题,想到了就很简单,其实也就是充分利用题设。n的规模为5*10^4,如果不进行一些处理直接上O(n^2)算法肯定会超时,但是题目里有个很重要的条件,那就是如果存在长度为100的回文子序列,只要输出这个即可,那么在最糟糕的情况下,多长长度的字符串才可能出现长度为100的回文子序列呢?答案是2600,为什么呢?因为小写字母就只有26个~~~2600个字符串肯定会出现长度为100的由单个字符组成的回文,也就是说如果n>=2600,那么只要简单统计一下,输出答案即可,否则的话进行O(n^2)复杂度的动态规划。不过很坑爹的是,如果我是在进行转移的时候直接用数组记录最长回文子序列,交上去总是Wrong answer on test25,一直找不到这是什么原因,代码在这里。改成传统的用DFS输出路径就A了。。。
代码:
#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> using namespace std; #define MAXN 2605 char s[50005],b[50005]; int dp[MAXN][MAXN]; int ans[30],cnt; void dfs(int l,int r) { if(l>r) return; if(l==r) b[cnt++]=s[l]; else if(s[l]==s[r]) { b[cnt++]=s[l]; dfs(l+1,r-1); b[cnt++]=s[r]; } else { if(dp[l][r-1]>dp[l+1][r]) dfs(l,r-1); else dfs(l+1,r); } } int main() { cin>>s; int n=strlen(s); if(n>2600) { for(int i=0;i<n;i++) { ans[s[i]-'0']++; if(ans[s[i]-'0']>=100) { for(int j=0;j<100;j++) cout<<s[i]; cout<<" "; return 0; } } } for(int i=0;i<n;i++) dp[i][i]=1; for(int l=1;l<n;l++) for(int i=0;i<n-l;i++) { int j=i+l; if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2; else dp[i][j]=max(dp[i+1][j],dp[i][j-1]); } cnt=0; dfs(0,n-1); if(cnt<100) cout<<b<<endl; else { for(int i=0;i<50;i++) cout<<b[i]; for(int i=49;i>=0;i--) cout<<b[i]; cout<<" "; } return 0; }