Codeforces 335B Palindrome

http://codeforces.com/contest/335/problem/B

题意:

 给定一个长度不超过5*10^4的只包含小写字母的字符串，要求你求它的回文子序列，如果存在长度为100的回文子序列，那么只要输出长度为一百的回文子序列即可，否则输出它的最长回文子序列.

思路:如果n>=2600，那么就一定会有单个字符构成的100长度的回文子序列。

否则当n<2600时就可以n^2 DP，然后dfs输出

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
char s[500005],b[500005];
int f[3005][3005],cnt,n,ans[50];
int read(){
    int t=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
    return t*f;
}
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 (f[l+1][r]>f[l][r-1]) dfs(l+1,r);
            else dfs(l,r-1);
        }
    }
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    if (n>=2600){
        for (int i=1;i<=n;i++){
         ans[s[i]-'a']++;
         if (ans[s[i]-'a']>=100){
            for (int j=1;j<=100;j++)
             printf("%c",s[i]);
            return 0; 
         }
        }
    }
    for (int i=1;i<=n;i++)
     for (int j=1;j<=n;j++)
      f[i][j]=0;
    for (int i=1;i<=n;i++)
     f[i][i]=1;
    for (int len=2;len<=n;len++)
     for (int i=1;i+len-1<=n;i++){
        int j=i+len-1;
        if (s[i]==s[j]) f[i][j]=std::max(f[i][j],f[i+1][j-1]+2);
        else f[i][j]=std::max(f[i][j],std::max(f[i+1][j],f[i][j-1]));
     } 
    dfs(1,n); 
    if (cnt<=100){
        for (int i=1;i<=cnt;i++)
         printf("%c",b[i]);
    }else{
        for (int i=1;i<=50;i++)
         printf("%c",b[i]);
        for (int i=50;i>=1;i--)
         printf("%c",b[i]); 
    }
    return 0;
}