[原创]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个叶子的树的种类

那么转移就是以当前点为根,左右子树方案数的乘积,

dp[n][m]=∑i∑jdp[i][j]∗dp[n−1−i][m−j]dp[n][m]=\sum_{i} \sum_{j} dp[i][j]*dp[n-1-i][m-j]

我开始采取记忆化的方式，然后处理答案要交表，然后发现时间比较快 交完就wa，补题的时候发现数据范围描述有误。。。

但其实如果我输出不是dp[n][m]，而直接dfs(n,m)也就诶问题了，，，也算长个记性。。。

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

# define abs(x) (((x)>0)?(x):-(x))

const int N = 1000000+10;
const int MOD  = 1e9+7;

/******************************************/

LL dp[555][555];

LL dfs(int x,int y){
    if(dp[x][y]!=-1) return dp[x][y];
    if(x<y*2-1||x<=0||y<=0)      return dp[x][y]=0ll;

    int xx=x-1,yy=y;
    LL res = 0;
    res=(2ll*dfs(xx,yy))%MOD;
    for(int i=0;i<xx;i++)
        for(int j=1;j<yy;j++)
            res=(res+(1ll*dfs(i,j)*dfs(xx-i,yy-j))%MOD)%MOD;

    return dp[x][y]=res;
}

int main(){
    memset(dp,-1,sizeof(dp));
    dp[1][1]=1;
//    for(int i=1;i<=50;i++){
//        printf("{");
//        for(int j=1;j<50;j++)  printf("%9lld,",dp[i][j]);
//        printf("%9lld},\n",dp[i][50]);
//    }

    int n,m;
    while(~scanf("%d%d",&n,&m)) {
//        if(n<1||n>100||m<1||m>100) while(true);
        printf("%lld\n",dfs(n,m));
    }
    return 0;
}