【BZOJ3769】spoj 8549 BST again DP(记忆化搜索?)
搜索 DP 记忆 again BST SPOJ
2023-09-11 14:15:25 时间
【BZOJ3769】spoj 8549 BST again
Description
求有多少棵大小为n的深度为h的二叉树。(树根深度为0;左右子树有别;答案对1000000007取模)
Input
第一行一个整数T,表示数据组数。
以下T行,每行2个整数n和h。
Output
共T行,每行一个整数表示答案(对1000000007取模)
Sample Input
2
2 1
3 2
2 1
3 2
Sample Output
2
4
4
HINT
对于100%的数据,1<=n<=600,0<=h<=600,1<=T<=10
题解:直接列DP方程,设f[i][j]表示有i个节点,深度为j的二叉树个数,然后列出方程用前缀和优化转移即可(注意防重)。
然后光荣TLE了,正解貌似是记忆化搜索?不过懒得改了,卡了卡常数就过了。
#include <cstdio> #include <iostream> #include <cstring> using namespace std; typedef long long ll; const int P=1000000007; int n,m; int a[15],b[15]; int f[610][610],s[610][610]; inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f; } void init() { register int i,j,k; f[0][0]=s[0][0]=1; for(j=1;j<=m;j++) s[0][j]=1; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(i>=j) for(k=0;k<i;k++) f[i][j]=(f[i][j]+(ll)f[k][j-1]*s[i-k-1][j-1]+(ll)s[k][j-2]*f[i-k-1][j-1])%P; s[i][j]=(s[i][j-1]+f[i][j])%P; } } int main() { int i,T=rd(); for(i=1;i<=T;i++) a[i]=rd(),b[i]=rd()+1,n=max(n,a[i]),m=max(m,b[i]); init(); for(i=1;i<=T;i++) printf("%d\n",f[a[i]][b[i]]); return 0; }
相关文章
- Sunday算法实现内存快速搜索特征码(支持带问号)
- hdu2067 简单dp或者记忆化搜索
- Laravel 多 where 并搜索
- solr的搜索
- 64jqGrid - 在搜索中显示查询条件
- 个性化搜索召回模型设计--训练部分
- HDU 4111 Alice and Bob (博弈+记忆化搜索)
- Gym 101142C CodeCoder vs TopForces (搜索)
- UVa 10817 Headmaster's Headache (状压DP+记忆化搜索)
- Python如何搜索模块
- 【剑指offer】23二叉搜索树的后序遍历序列
- CSS3实现的苹果网站搜索框效果
- 思博伦协助改进海上搜索与救援行动
- [CareerCup] 4.5 Validate Binary Search Tree 验证二叉搜索树
- Vue经典实例之数据搜索、数据过滤(简单易懂)
- leetcode算法108.将有序数组转换为二叉搜索树