UVA1362 Exploring Pyramids

题目：Exploring Pyramids

思路：

看到dfs序就想到区间处理。

看到方案数就想到dp。

所以是区间dp。

令f[i][j]表示[i,j]这一段的方案数。

枚举第一棵子树和其他子树的断点。

转移：$f[i][j]=f[i][j]+f[i+1][k?1]?f[k][j]$

边界（只有一颗子树）：$f[i][j]=f[i][j]+f[i+1][j?1]$

注意有乘法的地方要用 long long。

代码：

#include<bits/stdc++.h>
using namespace std;#define maxn 300
#define md ((int)1e9)int n;
char a[maxn+5];
int f[maxn+5][maxn+5];int main() {
    while(~scanf("%s",a+1)){
    memset(f,0,sizeof(f));n=strlen(a+1);for(int i=1;i<=n;i++) f[i][i]=1;for(int i=n;i>=1;i--) {
    for(int j=i+1;j<=n;j++) {
    if(a[i]!=a[j]) continue;f[i][j]=(f[i][j]+f[i+1][j-1])%md;for(int k=i+2;k<=j-2;k++) {
    if(a[i]==a[k]) f[i][j]=(f[i][j]+f[i+1][k-1]*(long long)f[k][j]%md)%md;}}}printf("%d\n",f[1][n]);}return 0;
}