CH 5302 金字塔（区间DP）

CH 5302 金字塔

$ solution: $

很神奇的一道题目，当时看到还以为是一道字符串求回文子串的题目。但是数据范围很小，而且只知道回文串也不好做。但是我们观察可得，如果是深度搜索便利，那么它经过的子树应该是从左到右排列有序的，于是我们想到线性DP。然后我们发现似乎可以单独求某一段的便遍历方式然后合并，这就是区间DP的标志啊！于是我们考虑设 $ F[l][r] $ 表示从第 $ l $ 到第 $ r $ 个字符可以有的子树遍历方案（注意既然是子树遍历方案，那么 $ l $ 字符和 $ r $ 的字符一致，因为它们都表示是这颗子树的根节点）。但是这样我们的转移需要保证不重不漏的计算左右情况。

这里很重要：（可能代码很好码，但原理我们不能模糊带过！）根据经验我们要找一个基准点来保证不重不漏，而常规套路就是枚举一个分段 $ k $ （注意我们的这个 $ k $ 的字符要和两端字符一样！因为当前子树需要根！）使得 $ [l,k] $ 为第一颗子树（注意这颗子树此时还连着根）而 $ [k,r] $ 这一段是另外的随便什么遍历方式，于是我们需要保证 $ [l,k] $ 为一颗子树（因为它现在还连着根），不能让它划分为连着根的多颗子树的形式，于是我们强制连边使 $ [l+1,k-1] $ 为一颗真正的不连边的子树，而强制连的边就是 $ e(l,l+1) $ 或者说 $ e(r,r-1) $ 。于是我们需要保证 $ l+1 $ 的字符和 $ k-1 $ 的字符一致（因为它们都表示是这颗子树的根节点）。然后我们就可转移了！

$ F[l][r]=\sum^{k\leq r}_{k=l+2} {f[l+1][k-1]\times f[k][r] }_{条件：s[l+1]s[k-1],s[k]s[r]} $

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define inf 0x7fffffff

#define rg register int

using namespace std;

const int mod=1e9;

int n;

int f[305][305];

string s;

inline int qr(){

	register char ch; register bool sign=0; rg res=0;

	while(!isdigit(ch=getchar())) if(ch=='-')sign=1;

	while(isdigit(ch)) res=res*10+(ch^48),ch=getchar();

	return sign?-res:res;

}

inline int solve(int l,int r){

	if(l==r)return 1;

	if(f[l][r]>=0)return f[l][r];

	else f[l][r]=0;

	for(rg k=l+2;k<=r;++k)

		if(s[l+1]==s[k-1]&&s[k]==s[r])

			f[l][r]=(f[l][r]+(ll)solve(l+1,k-1)*solve(k,r)%mod)%mod;

	return f[l][r];

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	cin>>s; n=s.size(); s=' '+s;

	memset(f,-1,sizeof(f));

	printf("%d\n",solve(1,n));

	return 0;

}

巴特西

CH 5302 金字塔（区间DP）