hdu-4632-Palindrome subsequence

指定された文字列の回文サブストリングの個数(文字列長==1000、合計T(=50)グループのテストデータを求めて、異なる位置の同じ文字列は異なっています.)
テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4632
——>>d[i][j]を設定して区間[i,j]内の回文部分列の個数を表し、
状態移行方程式:d[i][j]=(d[i＋1][j]+d[i]、[j-1]-d[i＋1]、[j-1]%mod;
両端の文字が同じであれば、両端の文字を両端とする回文のサブストリングの個数を加えます.この場合(i,j)には回文列があり、両端も回文列に違いないので、この回文のサブストリングの個数はd［i＋1］［j−1］です.
注意:型取りのため、状態移行方程式の計算にはマイナスが発生する可能性があります.
 

#include <cstdio>

#include <cstring>



using namespace std;



const int maxn = 1000 + 10;

const int mod = 10007;

int d[maxn][maxn];

char S[maxn];



int main()

{

    int T, kase = 1, i, j, k;

    scanf("%d", &T);

    while(T--){

        scanf("%s", S);

        int len = strlen(S);

        memset(d, -1, sizeof(d));

        for(i = 0; i < len; i++) d[i][i] = 1;

        for(i = 0; i < len-1; i++) d[i][i+1] = S[i] == S[i+1] ? 3 : 2;

        for(k = 2; k < len; k++){

            for(i = 0; i+k < len; i++){

                j = i + k;

                d[i][j] = (d[i+1][j] + d[i][j-1] - d[i+1][j-1]) % mod;

                if(d[i][j] < 0) d[i][j] += mod;

                if(S[i] == S[j]) d[i][j] = (d[i][j] + d[i+1][j-1] + 1) % mod;

            }

        }

        printf("Case %d: %d
", kase++, d[0][len-1]);

    }

    return 0;

}

記憶化検索の書き方は、C+843 ms、G++TLE:
 
 

#include <cstdio>

#include <cstring>



using namespace std;



const int maxn = 1000 + 10;

const int mod = 10007;

int d[maxn][maxn];

char S[maxn];



int dp(int i, int j){

    int& ans = d[i][j];

    if(ans != -1) return ans;

    if(i + 1 == j){

        if(S[i] == S[j]) return ans = 3;

        else return ans = 2;

    }

    if(i == j) return ans = 1;

    if(S[i] == S[j]) ans = dp(i+1, j-1) + 1;

    else ans = 0;

    ans = (ans + dp(i, j-1) + dp(i+1, j) - dp(i+1, j-1)) % mod;

    if(ans < 0) ans += mod;

    return ans;

}



int main()

{

    int T, kase = 1;

    scanf("%d", &T);

    while(T--){

        scanf("%s", S);

        int len = strlen(S);

        memset(d, -1, sizeof(d));

        printf("Case %d: %d
", kase++, dp(0, len-1));

    }

    return 0;

}