[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 M: qwb与二叉树 [记忆化dp]【动态规划】
[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 M: qwb与二叉树 [记忆化dp]【动态规划】
2017-06-03 03:04:48 Tabris_ 阅读数:467
博客爬取于2020-06-14 22:40:10
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849797
题目链接:http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=12
——————————————————————————————————————————
Problem M: qwb与二叉树
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 159 Solved: 35
[Submit][Status][Web Board]
Description
某一天,qwb正在上数据结构课。老师在讲台上面讲着二叉树,qwb在下面发着呆。
突然qwb想到一个问题:对于一棵n个无编号节点,m个叶子的有根二叉树,有多少种形态呐?你能告诉他吗?
Input
多组输入,处理到文件结束,大约有104组数据。
每一组输入一行,两个正整数n,m(0≤m≤n≤50),意义如题目所述。
Output
每一行输出一个数,表示相应询问的答案,由于答案可能很大,请将答案对109+7取模后输出。
Sample Input
4 2
10 5
Sample Output
6
252
HINT
样例1的6种形态:
——————————————————————————————————————————
心态爆炸的一道题,现场后2hours wa到死… 其实是题目描述错了1~50 但后台数据是0~50,后来修改了
题目而言是好题目,
设dp[i][j]是i个节点j个叶子的树的种类
那么转移就是以当前点为根,左右子树方案数的乘积,
我开始采取记忆化的方式,然后处理答案要交表,然后发现时间比较快 交完就wa,补题的时候发现数据范围描述有误。。。
但其实如果我输出不是dp[n][m],而直接dfs(n,m)也就诶问题了,,,也算长个记性。。。
附本题代码
——————————————————————————————————————————
1 | # include <bits/stdc++.h> |