CFR 245 H. Queries for Number of Palindromes ( DP, Inclusion Exclusion, Palindrome, IO = = )

Problem - 245H - Codeforces

題意：
給一個字串。接著 Q 筆詢問給左界右界，求對應的子字串中有多少回文子字串。

資料規模：
字串長度 1 ≤ | S | ≤ 5000
1 ≤ Q ≤ 1e6
時間限制：2500 ms
空間限制：256 MB

解法：
先用 O( N ^ 2 ) 預處理 is_pal[ l ][ r ]，表示 s[ l, r ] 是否為回文。接著就能預處理答案 dp[ l ][ r ]，表示 s[ l, r ] 中有多少回文子字串。考慮非 base case 會有以下轉移：
dp[ l, r ] = dp[ l ][ r - 1 ] + dp[ l + 1 ][ r ] - dp[ l + 1 ][ r - 1 ] + is_pal[ l ][ r ]

時間 / 空間複雜度：
O( N ^ 2 )

注意：
用 cin, cout 處理詢問絕對 TLE = = ( 翻桌

string seq;

void init(){
  cin >> seq;
}

bool is_pal[ 5000 + 1 ][ 5000 + 1 ];
int dp[ 5000 + 1 ][ 5000 + 1 ];

void preprocess(){
  for( int i = 0; i < seq.size(); ++i ){
    is_pal[ i ][ i ] = dp[ i ][ i ] =  1;
  }
  for( int i = 0; i + 1 < seq.size(); ++i ){
    if( seq[ i ] == seq[ i + 1 ] ){
      is_pal[ i ][ i + 1 ] = dp[ i ][ i + 1 ] = 1;
    }
  }
  for( int len = 3; len <= seq.size(); ++len ){
    for( int i = 0; i + len <= seq.size(); ++i ){
      if( seq[ i ] == seq[ i + len - 1 ] ){
        is_pal[ i ][ i + len - 1 ] = is_pal[ i + 1 ][ i + len - 2 ];
      }
    }
  }
  for( int len = 2; len <= seq.size(); ++len ){
    for( int i = 0; i + len <= seq.size(); ++i ){
      dp[ i ][ i + len - 1 ] = dp[ i ][ i + len - 2 ] + dp[ i + 1 ][ i + len - 1 ] - dp[ i + 1 ][ i + len - 2 ] + is_pal[ i ][ i + len - 1 ];
    }
  }
}

void solve(){
  int Q; cin >> Q;
  for( int kase = 0; kase < Q; ++kase ){
    int ql, qr; scanf( "%d%d", &ql, &qr ); // cin >> ql >> qr; --ql, --qr;
    printf( "%d\n", dp[ ql - 1 ][ qr - 1 ] ); // cout << dp[ ql - 1 ][ qr - 1 ] << endl;
  }
}