codeforces H. Queries for Number of Palindromes（区间dp）

题目链接：http://codeforces.com/contest/245/problem/H

题意：给出一个字符串还有q个查询，输出每次查询区间内回文串的个数。例如aba->(aba,a,b,a)有4个

题解：如果遇到区间而且数又不大n*n能存下来的可以考虑一下用区间dp，然后区间dp一般都是可以通过

预处理来减少for的层数，这里可以预处理一下Is[i][j]表示i，j区间是否是回文串然后dp转移方程就显而易见了。

dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+Is[i][j];

#include <iostream>

#include <cstring>

using namespace std;

const int M = 5e3 + 10;

char s[M];

bool Is[M][M];

int dp[M][M];

int main() {

    int q;

    scanf("%s" , s);

    int len = strlen(s);

    memset(Is , false , sizeof(Is));

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

        Is[i][i] = true;

    }

    for(int l = 1 ; l < len ; l++) {

        for(int i = 0 ; i < len && i + l < len ; i++) {

            int j = i + l;

            if(s[i] == s[j]) {

                if(l == 1) {

                    Is[i][j] = true;

                }

                else {

                    if(Is[i + 1][j - 1]) {

                        Is[i][j] = true;

                    }

                }

            }

        }

    }

    memset(dp , 0 , sizeof(dp));

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

        dp[i][i] = 1;

    }

    for(int l = 1 ; l < len ; l++) {

        for(int i = 0 ; i < len && i + l < len ; i++) {

            int j = i + l;

            if(l == 1) {

                dp[i][j] = dp[i][i] + dp[j][j] + Is[i][j];

            }

            else {

                dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + Is[i][j];

            }

        }

    }

    scanf("%d" , &q);

    while(q--) {

        int l , r;

        scanf("%d%d" , &l , &r);

        printf("%d\n" , dp[l - 1][r - 1]);

    }

    return 0;

}

巴特西

codeforces H. Queries for Number of Palindromes（区间dp）

最新文章

热门文章