题目vj链接

题面：

题意：
给定一个字符串，每次询问 [ l , r ] [l,r] [l,r]的子串中有多少个回文子串。

题解：
我们设 d p [ l ] [ r ] dp[l][r] dp[l][r]为 [ l , r ] [l,r] [l,r]的回文子串的个数，那么 d p [ l ] [ r ] = d p [ l ] [ r − 1 ] + d p [ l + 1 ] [ r ] − d p [ l + 1 ] [ r − 1 ] + [ S ( l , r ) = = 回 文 串 ] dp[l][r]=dp[l][r-1]+dp[l+1][r]-dp[l+1][r-1]+[S(l,r)==回文串] dp[l][r]=dp[l][r−1]+dp[l+1][r]−dp[l+1][r−1]+[S(l,r)==回文串]。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=5010;
const int maxm=100100;
const int maxp=100100;
const int up=100100;

int dp[maxn][maxn];
char str[maxn];
bool ha[maxn][maxn];

int main(void)
{
    int t;
    scanf("%s%d",str+1,&t);
    int n=strlen(str+1);

    for(int i=1;i<=n;i++)
    {
        ha[i][i]=true;
        dp[i][i]=1;
        if(i>1)
        {
            if(str[i]==str[i-1])
                ha[i-1][i]=true,dp[i-1][i]=3;
            else dp[i-1][i]=2;
        }

    }
    for(int len=3;len<=n;len++)
    {
        for(int l=1;l<=n-len+1;l++)
        {
            int r=l+len-1;
            dp[l][r]=dp[l][r-1]+dp[l+1][r]-dp[l+1][r-1];
            if(ha[l+1][r-1]&&str[l]==str[r])
                ha[l][r]=true,dp[l][r]++;
        }
    }

    int x,y;
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",dp[x][y]);
    }
    return 0;
}