CFR 245 H. Queries for Number of Palindromes ( DP, Inclusion Exclusion, Palindrome, IO = = )
題意:
給一個字串。接著 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; } }