CFR 159 D. Palindrome pairs ( DP )

Problem - D - Codeforces
題意：
給一個字串s，求有多少整數組 ( a, b, x, y ) 滿足 s[ a .. b ] 為回文且 s[ x .. y ] 為回文。
解法：
先O( | S | ^ 2 )預處理使得可以用常數時間判斷一個子字串是否為回文。再額外預處理前綴和 spal[ t ] 存儲前 t 個字母的子字串中的回文數。裡接著考慮動態規劃
dp[ i ] : 考慮完 i 個字元時的答案
dp[ i ] = dp[ i - 1 ] + SIGMA{ spal[ j ] | 所有 j 滿足 s[ j .. i ] 為回文 }

string seq;

void init(){
    cin >> seq;
}

vvi is_pal; // [ l, r ]
vi spal;
vl dp;

void preprocess(){
    is_pal = vvi( seq.size() + 1, vi( seq.size() + 1 ) );
    for( int i = 0; i < seq.size(); ++i )
        is_pal[ i ][ i ] = 1;
    for( int i = 0; i + 2 <= seq.size(); ++i )
        if( seq[ i ] == seq[ i + 1 ] )
            is_pal[ i ][ i + 1 ] = 1;
    for( int len = 1; len + 2 <= seq.size(); ++len )
        for( int i = 1; i + len < seq.size(); ++i )
            if( is_pal[ i ][ i + len - 1 ] )
                if( seq[ i - 1 ] == seq[ i + len ] )
                    is_pal[ i - 1 ][ i + len ] = 1;
    spal = vi( seq.size() + 1 );
    for( int i = 0; i < seq.size(); ++i )
        for( int j = i; j < seq.size(); ++j )
            spal[ j + 1 ] += is_pal[ i ][ j ];
    for( int i = 0; i < seq.size(); ++i )
        spal[ i + 1 ] += spal[ i ];
    dp = vl( seq.size() + 1 );
    for( int i = 0; i < seq.size(); ++i ){
        dp[ i + 1 ] += dp[ i ];
        for( int j = 0; j <= i; ++j )
            if( is_pal[ j ][ i ] )
                dp[ i + 1 ] += spal[ j ];
    }
}

void solve(){
    cout << dp[ ( int ) seq.size() ] << endl;
}