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[],b[];

int f[][],cnt,n,ans[];

int read(){

    int t=,f=;char ch=getchar();

    while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

    while (''<=ch&&ch<=''){t=t*+ch-'';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+,r-);

            b[++cnt]=s[r];

        }else{

            if (f[l+][r]>f[l][r-]) dfs(l+,r);

            else dfs(l,r-);

        }

    }

}

int main(){

    scanf("%s",s+);

    n=strlen(s+);

    if (n>=){

        for (int i=;i<=n;i++){

         ans[s[i]-'a']++;

         if (ans[s[i]-'a']>=){

            for (int j=;j<=;j++)

             printf("%c",s[i]);

            return ;

         }

        }

    }

    for (int i=;i<=n;i++)

     for (int j=;j<=n;j++)

      f[i][j]=;

    for (int i=;i<=n;i++)

     f[i][i]=;

    for (int len=;len<=n;len++)

     for (int i=;i+len-<=n;i++){

        int j=i+len-;

        if (s[i]==s[j]) f[i][j]=std::max(f[i][j],f[i+][j-]+);

        else f[i][j]=std::max(f[i][j],std::max(f[i+][j],f[i][j-]));

     }

    dfs(,n);

    if (cnt<=){

        for (int i=;i<=cnt;i++)

         printf("%c",b[i]);

    }else{

        for (int i=;i<=;i++)

         printf("%c",b[i]);

        for (int i=;i>=;i--)

         printf("%c",b[i]);

    }

    return ;

}