金字塔（區間dp）

題目描述

連結

雖然探索金字塔是極其老套的劇情，但是有一隊探險家還是到了某金字塔腳下。

經過多年的研究，科學家對這座金字塔的内部結構已經有所了解。

首先，金字塔由若幹房間組成，房間之間連有通道。

如果把房間看作節點，通道看作邊的話，整個金字塔呈現一個有根樹結構，節點的子樹之間有序，金字塔有唯一的一個入口通向樹根。

并且，每個房間的牆壁都塗有若幹種顔色的一種。

探險隊員打算進一步了解金字塔的結構，為此，他們使用了一種特殊設計的機器人。

這種機器人會從入口進入金字塔，之後對金字塔進行深度優先周遊。

機器人每進入一個房間（無論是第一次進入還是傳回），都會記錄這個房間的顔色。

最後，機器人會從入口退出金字塔。

顯然，機器人會通路每個房間至少一次，并且穿越每條通道恰好兩次（兩個方向各一次）， 然後，機器人會得到一個顔色序列。

但是，探險隊員發現這個顔色序列并不能唯一确定金字塔的結構。

現在他們想請你幫助他們計算，對于一個給定的顔色序列，有多少種可能的結構會得到這個序列。

因為結果可能會非常大，你隻需要輸出答案對 1 0 9 10^9 109 取模之後的值。

輸入描述:

輸入僅一行，包含一個字元串 S S S，長度不超過 300 300 300，表示機器人得到的顔色序列。

輸出描述:

輸出一個整數表示答案。

輸入

ABABABA
           

輸出

思路

之前做的區間dp題目都是：一個大區間可以看作是兩個小區間合并。

如果這道題規定，金字塔内部結構是一棵二叉樹，那麼和普通的區間dp就一樣了（因為一個區間最多可以看作是兩個區間合并）。

可是它是多叉樹，區間dp的時候要合并多個區間就沒法搞了。

STD是，确定第一棵子樹 d f s dfs dfs 序的範圍。 也就是說，本來是多個區間合并，把它看作是第一個區間和剩下的所有區間合并。

這樣枚舉第一個區間的範圍，就不會漏解。而且又轉化為我們熟悉的兩個區間合并了。

f [ i ] [ j ] = ∑ s [ i ] = s [ k ] , i ≤ k ≤ j f [ i + 1 ] [ k − 1 ] × f [ k ] [ j ] f[i][j]=\sum_{s[i]=s[k],i \le k \le j} f[i+1][k-1] \times f[k][j] f[i][j]=s[i]=s[k],i≤k≤j∑​f[i+1][k−1]×f[k][j]

#include<bits/stdc++.h>
using namespace std;
const int N=310,mod=1e9;
char s[N]; int n,f[N][N];

signed main(){
	cin>>(s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++) f[i][i]=1;
	for(int len=2;len<=n;len++)
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			for(int k=i;k<=j;k++) if(s[i]==s[k])
				f[i][j]=(f[i][j]+f[i+1][k-1]*f[k][j])%mod;
		}
	cout<<f[1][n]<<"\n";
}