题解：P10956 金字塔
luxiaomao
·
·
题解
P10956 简单区间 DP
竟然一遍过还可以写题解。
Problem
一棵 n 个点的树，每个点被染上若干种颜色中的一种，给出用欧拉序遍历这棵树时得到的颜色序列，求树的可能的形态数。
Solution
比较板地设 $f_{l,r}$ 为区间 $[l,r]$ 的答案。然后根据乘法原理可以写出：
```cpp
for(int i = 1;i <= n;i++)f[i][i] = 1,g[i][i] = 1;
for(int k = 3;k <= n;k+=2)
for(int l = 1,r = k;r <= n;l++,r++)
{
if(s[l] != s[r])
continue;
f[l][r] = f[l+1][r-1];
for(int i = l+1;i < r;i++)
if(s[i] == s[l])
(f[l][r] += f[l][i] * f[i][r] % mod) %= mod;
}
```
但是答案偏大，手推了一下发现，假设在一种形态中根有三个孩子，在枚举断点的时候实际上会枚举两次，也就是这种形态的贡献被多算了一次。
我们设 $g_{l,r}$ 表示：区间 $[l,r]$，中途不准跑回根节点的形态数。
把 $f_{l,r} = \sum f_{l,i} \times f_{i,r}$ 改为 $f_{l,r} = \sum g_{l,i} \times g_{i,r}$。
但是这样答案又小了，发现这样只统计了两个孩子的情况，三个孩子没被考虑到。
断点将一个区间割为左右区间。我们应该允许其中一个区间中途跑回根节点，另一个不能跑回根节点，这样就可以覆盖所有情况而不重复了，具体实现请看代码。
特殊地，若 $s_l \not= s_r$，$f_{l,r} = 0$。
## Code
```cpp
#include<bits/stdc++.h>
#define int long long
#define N 305
using namespace std;
const int mod = 1e9;
int n;
char s[N];
int f[N][N],g[N][N];
signed main()
{
scanf("%s",s+1);
n = strlen(s+1);
for(int i = 1;i <= n;i++)f[i][i] = 1,g[i][i] = 1;
for(int k = 3;k <= n;k+=2)
for(int l = 1,r = k;r <= n;l++,r++)
{
if(s[l] != s[r])
continue;
g[l][r] = f[l+1][r-1];
f[l][r] = f[l+1][r-1];
for(int i = l+1;i < r;i++)
if(s[i] == s[l])
(f[l][r] += g[l][i] * f[i][r] % mod) %= mod;
}
printf("%lld\n",f[1][n]);
return 0;
}
```