toj 26 最長回文

domen111

http://toj.twbbs.org/oj/chal/2782/

為什麼會TLE?

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

char s[3010];

int len;

int dp[3010][3010];

int solve(int l,int r)

{

    if(l>r) return 0;

    if(l==r) return 1;

    if(s[l]==s[r])

        return dp[l][r] = solve(l+1,r-1) + 2;

    else

        return dp[l][r] = max(solve(l+1,r),solve(l,r-1));

}

int main()

{

    int T;

    scanf("%d",&T);

    getchar();

    while(T--)

    {

        gets(s);

        len=strlen(s);

        memset(dp,-1,sizeof dp);

        printf("%d\n",solve(0,len-1));

    }

}

Sylveon

本題有O(N)作法，參考 Z value

domen111

Sylveon 發表於 2014-6-7 18:40
本題有O(N)作法，參考 Z value

Z value是什麼? 有沒有參考網址? google查一大堆無關的東西

allenwhale

其實這題不是Z VALUE的題目
因為他的回文不需要連在一起
可以簡單用lcm解決，我忘記O(N^2)會不會過了
我當初是用O(nlgn)的解法

allenwhale

經過我的實測O(N^2)的lcm只有50分