$金字塔$金字塔

Description

链接
虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。首先，金字塔由若干房间组成，房间之间连有通道。如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。并且，每个房间的墙壁都涂有若干种颜色的一种。
探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。最后，机器人会从入口退出金字塔。
显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。因为结果可能会非常大，你只需要输出答案对10^9 取模之后的值。

Solution

区间 $dp$dp

容易想到设 $dp[l,r]$dp[l,r]表示 $[l,r]$[l,r]的方案数, 当 $S_l=\ne S_r$Sl​≠​=Sr​时, 显然 $dp[l,r]=0$dp[l,r]=0
阶段状态已经为 $[l,r]$[l,r], 那么考虑怎么 划分区间, 即 决策

一段区间即表示一颗子树, 而这棵子树可能包含多颗更小的子树, 即可能划分为多个子区间(子问题),
则可以在这段区间中找到合法的分界点 $k$k, 使得 $S_l=S_k=S_r$Sl​=Sk​=Sr​, 将这个区间划分为 $[l+1,k-1],[k,r]$[l+1,k−1],[k,r]这两个区间,
也可以理解为: 将 $[l+1,k-1](k\in [l+2,r\left]\right)$[l+1,k−1]  (k∈[l+2,r]) 作为第一颗子树, 然后 $[k,r]$[k,r]作为另外一部分子树, 由于每次第一颗子树大小不等, 可以保证计数 不重不漏.

而当 $S_i==S_j$Si​==Sj​时, 可以使得 $dp[i,j]=dp[i+1,j-1]$dp[i,j]=dp[i+1,j−1], 表示以 $S_i$Si​为根的只有一个儿子的子树

遵循以上信息, 可以得出 $dp[i,j]$dp[i,j]表示区间 $[i,j]$[i,j]组成的子树的方案数, 其中 $S_l和S_r$Sl​和Sr​为进入和出去产生的字符,
状态转移方程自然也就出来了 $\downarrow$↓

$dp[i,j]=\{\begin{array}{c}1(i==j)\\ 0(S_i!=S_j\mid \mid i\>j)\\ dp[i+1,j-1]+{\sum }_{k=l+2}^{r-2}dp[i+1,k-1]\ast dp[k,r](S_i==S_j)\end{array}$dp[i,j]=⎩⎪⎨⎪⎧​1              (i==j)0              (Si​  !=Sj​  ∣∣  i>j)dp[i+1,j−1]+∑k=l+2r−2​dp[i+1,k−1]∗dp[k,r]                (Si​==Sj​)​
使用递归实现即可

Attention

上方的第三个状态转移方程在程序中写成
$dp[i,j]={\sum }_{k=l+2}^{r}dp[i+1,k-1]\ast dp[k,r](S_i==S_j)$dp[i,j]=∑k=l+2r​dp[i+1,k−1]∗dp[k,r]                (Si​==Sj​)

这是因为 $k=r-1$k=r−1时, $右=dp[i+1,r-2]\ast dp[r-1,r]=0$右=dp[i+1,r−2]∗dp[r−1,r]=0

$k=r$k=r时, $右=dp[i+1,r-1]\ast dp[r,r]=dp[i+1,r-1]$右=dp[i+1,r−1]∗dp[r,r]=dp[i+1,r−1]

Code

#include<bits/stdc++.h>
#define reg register

const int maxn = 305;
const int mod = 1e9;


char S[maxn];
int N;
int dp[maxn][maxn];

int Dp(int l, int r){
        if(l > r) return 0;
        if(l == r) return 1;
        if(S[l] != S[r]) return dp[l][r] = 0;
        if(~dp[l][r]) return dp[l][r];
        dp[l][r] = 0;
        for(reg int k = l+2; k <= r; k ++) dp[l][r] = (1ll*dp[l][r] + 1ll * Dp(l+1, k-1) * Dp(k, r)) % mod;
// if(S[l] == S[r]) dp[l][r] += dp[l+1][r-1]==-1?0:dp[l+1][r-1];
        return dp[l][r];
}

int main(){
        freopen("pyr.in", "r", stdin);
        freopen("pyr.out", "w", stdout);
        scanf("%s", S+1);
        N = strlen(S+1);
        memset(dp, -1, sizeof dp);
        Dp(1, N);
        printf("%d\n", dp[1][N]);
        return 0;
}