uva live 3516 - Exploring Pyramids

点击打开链接

题意：给出一棵多叉树，每个结点的任意两个子节点都有左右之分。从根节点开始，每次尽量往左走，走不通就回溯，把遇到的字母顺序记录下来，可以得到一个序列。给定一个序列，问有几种满足的多叉树。

思路：

1 设输入的序列为S，dp[i][j]为子序列Si,Si+1...Sj对应的树的个数，则边界条件是dp[i][i] = 1，且Si不等于Sj时dp[i][j] = 0。

2 这样在非边界情况下，Si = Sj递推的关系为dp[i][j] = sum{dp[i+1][k-1]*dp[k][j]} i+2 <= k <= j。 

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int MAXN = 310;
const int MOD = 1e9;

char str[MAXN];
int64 ans[MAXN][MAXN];

int64 solve(int i , int j){
    if(i == j)
		return 1;
	if(str[i] != str[j])
		return 0;
	if(ans[i][j] >= 0) 
		return ans[i][j];
	ans[i][j] = 0;
	for(int k = i+2 ; k <= j ; k++)
		ans[i][j] += (solve(i+1 , k-1)*solve(k , j))%MOD;
    return ans[i][j];	
}

int main(){
    while(scanf("%s" , str) != EOF){
		memset(ans , -1 , sizeof(ans));
		printf("%lld\n" , solve(0 , strlen(str)-1));
	}
	return 0;
}