UVa 1362(LA 3516) Exploring Pyramids

本文主要是介绍UVa 1362(LA 3516) Exploring Pyramids，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

          依旧是《训练指南》上的一道例题。思路大致相同，即设有一个序列S(i),S(i+1),S(i+2)...S(j)，d[i,j]为所求的解。当S(i)==S(k),i<k<=j 时,说明在k回到根，那么S(i+1)...S(k-1)构成一棵独立的子树(当然也可能并不是子树)。那么d[i,j]就要加上d[i+1,k-1]*d[k,j]，不断递增k，每遇到一个k,d[i,j]+=d[i+1,k-1]*d[k,j]直到k>j。最后的d[i,j]就是序列S(i)..S(j)的解。那么题目最终的解即为d[0,n-1],n为序列的长度。

不过，在具体的解法上，我和书上的做法不一样。书上使用的是递归，而我使用了从底向下的方法。显然d[i,i]=1，然后采用类似于最优二叉排序树的解法，依次求出j-i=1,j-i=2....j-i=n-1时的d[i,j]的值。最后输出d[0,n-1]即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define MAX 300+5
#define MOD 1000000000
using namespace std;long long ans[MAX][MAX];int main()
{string S;while(cin>>S){int n=S.size();memset(ans,0,sizeof(ans));for(int i=0;i<n;++i) ans[i][i]=1;//单个节点的树都为一种情况for(int i=1;i<n;++i){//两个坐标间的差值for(int j=0;j+i<n;++j){for(int k=1;k<=i;++k){//从j+1遍历到j+iif(S[j]==S[j+k]){ans[j][j+i]+=ans[j+1][j+k-1]*ans[j+k][j+i];ans[j][j+i]%=MOD;}}}}cout<<ans[0][n-1]<<endl;}return 0;
}

这篇关于UVa 1362(LA 3516) Exploring Pyramids的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---