首页 > 代码库 > uva 1362 - Exploring Pyramids(区间dp)
uva 1362 - Exploring Pyramids(区间dp)
题目连接:uva 1362 - Exploring Pyramids
题目大意:给出一个字符串,问有多少种多叉树德前序遍历(这里每经过一个节点,该节点的值即要被算入,回溯的也要)满足该字符串。
解题思路:dp[i][j]表示从i到j的位置可以用多少种多叉树表示。转移方程:dp[i][j]=∑k=i+2jdp[i+1][k?1]?dp[k][j]。
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 305;
const ll MOD = 1e9;
char s[N];
ll dp[N][N];
ll solve (int x, int y) {
if (x == y)
return dp[x][y] = 1;
if (s[x] != s[y])
return dp[x][y] = 0;
ll& ans = dp[x][y];
if (ans >= 0)
return ans;
ans = 0;
for (int i = x+2; i <= y; i++) {
if (s[x] == s[i])
ans = (ans + solve(x+1, i-1) * solve(i, y))%MOD;
}
return ans;
}
int main () {
while (scanf("%s", s) == 1) {
memset(dp, -1, sizeof(dp));
printf("%lld\n", solve(0, strlen(s)-1));
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。