首页 > ACM题库 > HDU-杭电 > HDU 4359-Easy Tree DP?-动态规划-[解题报告]HOJ
2015
05-23

HDU 4359-Easy Tree DP?-动态规划-[解题报告]HOJ

Easy Tree DP?

问题描述 :

A Bear tree is a binary tree with such properties : each node has a value of 20,21…2(N-1)(each number used only once),and for each node ,its left subtree’s elements’ sum<its right subtree’s elements’ sum(if the node hasn’t left/right subtree ,this limitation is invalid).
You need to calculate how many Bear trees with N nodes and exactly D deeps.

输入:

First a integer T(T<=5000),then T lines follow ,every line has two positive integer N,D.(1<=D<=N<=360).

输出:

First a integer T(T<=5000),then T lines follow ,every line has two positive integer N,D.(1<=D<=N<=360).

样例输入:

2
2 2
4 3

样例输出:

Case #1: 4
Case #2: 72

题目大意:

给你n个节点,第i个节点的权值为2^(i-1),求满足以下条件的深度为d的二叉树的个数(最后结果对maxmod=109+7取余):左子树权值之和小于右子树权值之和,当只有一个子树时可以不满足这个条件。

5000个测试点,n,d<=360

题解:

1.首先注意f[n][d]的结果是一定的,所以先预处理出来所有的f[n][d]。然后对每个测试点直接输出f[n][d]即可。(一开始一直T就是因为没有预处理)

2.由于2^i的特殊性质,题目中有一个条件可以转化:左子树和<右子树和等价于左子树最大值<右子树最大值。

3.f[i][j]表示i个节点组成深度不超过j的满足条件的二叉树个数,则最后答案是(f[n][d]+maxmod-f[n][d-1])%maxmod。(注意在反复取余后最后结果f[n][d]可能会小于f[n][d-1])

先考虑只有一个子树的情况:(c[i][j]表示组合数)

个数为c[i][i-1]*2*f[i-1][j-1],其中c[i][i-1]表示选择i-1个节点做子树

在考虑有两个子树的情况

个数为c[i][i-1]*c[i-2][k]*f[k][j-1]*f[i-1-k][j-1](1<=k<=i-2),其中c[i][j-1]表示选择i-1个节点做子树。由于要满足左子树最大值<右子树最大值,所以选择的i-1个节点中最大的那个一定分配给右子树,所以左子树只能从i-2个节点中选k个做其节点,于是有c[i-2][k]。

综上,f[i][j]=c[i][i-1]*2*f[i-1][j-1]+c[i][i-1]*c[i-2][k]*f[k][j-1]*f[i-1-k][j-1](1<=k<=i-2)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=369;
const long long maxmod=1000000000+7;
long long f[maxn][maxn],c[maxn][maxn];
int n,m,z,sec;
int main()
{
    memset(f,0,sizeof(f));
    memset(c,0,sizeof(c));
    for(int i=1;i<=360;i++)
    {
        c[0][0]=1;
        c[i][0]=1;
    }
    for(int i=1;i<=360;i++)
     for(int j=1;j<=i;j++)
        c[i][j]=(c[i-1][j-1]+c[i-1][j])%maxmod;
    for(int j=1;j<=360;j++)
    f[1][j]=1;
    for(int i=2;i<=360;i++)
    for(int j=1;j<=360;j++)
    {
    f[i][j]=(c[i][i-1]*2*f[i-1][j-1])%maxmod;
    for(int k=1;k<=i-2;k++)
    f[i][j]=(f[i][j]+((c[i][i-1]*c[i-2][k])%maxmod)*((f[k][j-1]*f[i-1-k][j-1])%maxmod))%maxmod;
    }
    scanf("%d",&sec);
    for(int z=1;z<=sec;z++)
    {
        scanf("%d%d",&n,&m);
        printf("Case #%d: %I64d\n",z,(f[n][m]+maxmod-f[n][m-1])%maxmod);
    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/hyogahyoga/article/details/7852067