本文主要是介绍uva live 3516 Exploring Pyramids 区间DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// uva live 3516 Exploring Pyramids 区间DP
//
// 题目大意:
//
// 给你一个多叉树,每个节点是一个大写字母,从根节点走,按照先序遍历的
// 原则访问,不能访问则回溯,每次记录一下节点的字符,最后得到一个字符串.现
// 在给你一个字符串,问可能符合条件的多叉树的数量.
//
// 解题思路:
//
// 区间DP,我们注意到,从根节点出发,一定会再次回到根节点,那么我们可以设
// d(i,j) 是序列i到j段形成的符合条件的多叉树的数量,则
// i~j一定会有一个k使得s[i] = s[k]{因为一定要回到i}.所以问题就转化为i+1~k-1
// 的子树和k~j树中的另外一个部分.这两部分乘积的结果就是区间的答案.采用记忆化
// 搜索.用vis标记是否访问过.边界为d(i,i) = 1,s[i]!=s[j]时,d(i,j)=0,不要忘记
// 要回到根如果头和尾不相等,肯定回不去的.
//
// 感悟:
//
// 区间DP我知道,状态我想的到,但是状态的转移,不是非常清楚明白.继续加油吧~~~
// FIGHTING!!!#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;typedef long long ll;
const int MAX_N = 308;
const int MOD = 1000000000;int n;char s[MAX_N];
ll d[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N];ll dp(int x,int y){if (x > y)return d[x][y] = 0;if (x == y)return d[x][y] = 1;if (s[x]!=s[y])return 0;if (vis[x][y])return d[x][y];vis[x][y] = 1;ll& ans = d[x][y];ans = 0;for (int k=x+2;k<=y;k++){ // 注意，这里最少走两步，走一步就是自己到自己if (s[x] == s[k])ans = (ans + dp(x+1,k-1)%MOD * dp(k,y))%MOD;}return ans % MOD;}void solve(){memset(d,0,sizeof(d));memset(vis,0,sizeof(vis));printf("%lld\n",dp(0,strlen(s)-1));
}int main(){//freopen("1.txt","r",stdin);while(scanf("%s",s)!=EOF){solve();}
}
这篇关于uva live 3516 Exploring Pyramids 区间DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
