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;
}
时间: 2013-11-21
Tags: 序列, Algorithm

uva live 3516 - Exploring Pyramids的相关文章

UVa 1362 Exploring Pyramids:多叉树遍历&amp;amp;DP

1362 - Exploring Pyramids Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=469&page=show_problem&problem=4108 Archaeologists have discovered a new set of hidden caves in one of the Egy

UVa 10361 Automatic Poetry:字符串处理&amp;amp;两种读入方式

10361 - Automatic Poetry Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=96&page=show_problem&problem=1302 "Oh God", Lara Croft exclaims, "it's one of these dumb riddle

UVA之10361 - Automatic Poetry

Problem I Automatic Poetry Input: standard input Output: standard output Time Limit: 2 seconds Memory Limit: 32 MB   "Oh God", Lara Croft exclaims, "it's one of these dumb riddles again!"   In Tomb Raider XIV, Lara is, as ever, gunning

UVa 10602

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1543 类型:贪心 原题: Company Macrohard has released it's new version of editor Nottoobad, which can understand a few voice commands.

UVa 10392 Factoring Large Numbers:素因子分解

10392 - Factoring Large Numbers Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=100&page=show_problem&problem=1333 One of the central ideas behind much cryptography is that factoring

UVa 10182 Bee Maja:规律&amp;amp;O(1)算法

10182 - Bee Maja Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1123 Maja is a bee. She lives in a bee hive with thousands of other bees. This bee hive c

算法题之UVA 763

Fibinary Numbers The standard interpretation of the binary number 1010 is 8 + 2 = 10. An alternate way to view the sequence ``1010'' is to use Fibonacci numbers as bases instead of powers of two. For this problem, the terms of the Fibonacci sequence

算法题:UVa 11461 Square Numbers (简单数学)

11461 - Square Numbers Time limit: 1.000 seconds http://uva.onlinejudge.org/index.php? option=com_onlinejudge&Itemid=8&category=467&page=show_problem&problem=24 56 A square number is an integer number whose square root is also an integer.

UVa 10183 How Many Fibs? (统计斐波那契数个数&amp;amp;高精度)

10183 - How Many Fibs? Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1124 Recall the definition of the Fibonacci numbers:    f1 := 1    f2 := 2    fn :