Codeforces 835D(区间DP+字符串DP)

Codeforces 835D
首先我们知道:

  • 第$k$阶的回文串本身是回文串
  • 第$k$阶的回文串左右两边是第$k-1$阶的回文串

那么我们可以DP,设$dp(i,j)$为$[i,j]$为多少阶回文串
先判$[i,j]$是否回文,如果不是,那么$[i,j]$不构成任何阶的回文串;
否则$dp(i,j)=dp(i, i +\frac{ (j - i + 1)}{2} - 1)+1$,因为第$k$阶的回文串左右两边是第$k-1$阶的回文串
然后$[1, k-1]$阶的回文串一定包含了$[k, n]$的回文串,所以累加一下就行
然后区间DP用记忆化做

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 5000 + 10;
char s[MAXN];
int n, f[MAXN][MAXN], ans[MAXN];
int dp(int i, int j) {
if (f[i][j] >= 0) return f[i][j];
if (i > j) return f[i][j] = 0;
if (i == j) return f[i][j] = 1;
if (s[i] != s[j] || (i + 1 <= j - 1 && dp(i + 1, j - 1) == 0)) return f[i][j] = 0;
int a = dp(i, i + (j - i + 1) / 2 - 1);
return f[i][j] = a + 1;
}
void clean() {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) f[i][j] = -1;
ans[i] = 0;
}
}
void solve() {
n = strlen(s + 1);
clean();
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) dp(i, j);
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) ans[f[i][j]]++;
for (int i = n; i > 0; i--) ans[i] += ans[i + 1];
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}
int main() {
scanf("%s", s + 1), solve();
return 0;
}

------ 本文结束 ------