【CF245H】Queries for Number of Palindromes(字符串区间dp)

Queries for Number of Palindromes - 洛谷

# Queries for Number of Palindromes

## 题面翻译

题目描述

给你一个字符串s由小写字母组成，有q组询问，每组询问给你两个数，l和r，问在字符串区间l到r的字串中，包含多少回文串。

输入格式

第1行，给出s，s的长度小于5000
第2行给出q(1<=q<=10^6)
第2至2+q行 给出每组询问的l和r

输出格式

输出每组询问所问的数量。

## 题目描述

You've got a string $ s=s_{1}s_{2}...\ s_{|s|} $ of length $ |s| $ , consisting of lowercase English letters. There also are $ q $ queries, each query is described by two integers $ l_{i},r_{i} $ $ (1<=l_{i}<=r_{i}<=|s|) $ . The answer to the query is the number of substrings of string $ s[l_{i}...\ r_{i}] $ , which are palindromes.

String $ s[l...\ r]=s_{l}s_{l+1}...\ s_{r} $ $ (1<=l<=r<=|s|) $ is a substring of string $ s=s_{1}s_{2}...\ s_{|s|} $ .

String $ t $ is called a palindrome, if it reads the same from left to right and from right to left. Formally, if $ t=t_{1}t_{2}...\ t_{|t|}=t_{|t|}t_{|t|-1}...\ t_{1} $ .

## 输入格式

The first line contains string $ s $ $ (1<=|s|<=5000) $ . The second line contains a single integer $ q $ $ (1<=q<=10^{6}) $ — the number of queries. Next $ q $ lines contain the queries. The $ i $ -th of these lines contains two space-separated integers $ l_{i},r_{i} $ $ (1<=l_{i}<=r_{i}<=|s|) $ — the description of the $ i $ -th query.

It is guaranteed that the given string consists only of lowercase English letters.

## 输出格式

Print $ q $ integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.

## 样例 #1

### 样例输入 #1

```
caaaba
5
1 1
1 4
2 3
4 6
4 5
```

### 样例输出 #1

```
1
7
3
4
2
```

## 提示

Consider the fourth query in the first test case. String $ s[4...\ 6] $ = ?aba?. Its palindrome substrings are: ?a?, ?b?, ?a?, ?aba?.

核心思路

类似容斥dp

f[l][r]表示答案 = f[l][r-1] + [l+1][r] -f[l+1][r-1]+pd[l][r]

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5050;
int tot;
string a;
int n;
bool pd[5050][5050];
long long f[5050][5050];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>a;
	n = a.size();
	a = " "+a;
	for(int i = 1;i <= n;i++)pd[i][i] = 1;
	for(int i = 1;i <= n-1;i++)if(a[i] == a[i+1])pd[i][i+1] = 1;
	for(int i = 3;i <= n;i++){
		for(int l = 1,r = l+i-1;r <= n;l++,r++){
			pd[l][r] = (pd[l+1][r-1] == 1&&a[l] == a[r]?1:0);
		}
	}
	for(int i = 1;i <= n;i++){
		f[i][i] = 1;
	} 
	for(int i = 2;i <= n;i++){
		for(int l = 1,r = l+i-1;r <= n;l++,r++){
			f[l][r] = f[l][r-1]+f[l+1][r]-f[l+1][r-1]+pd[l][r];
		}
	}
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<f[l][r]<<"\n";
	}
	return 0;
}