首页 > ACM题库 > HDU-杭电 > hdu 2292 Minimum Heap-动态规划[解题报告]C++
2014
01-05

hdu 2292 Minimum Heap-动态规划[解题报告]C++

Minimum Heap

问题描述 :

Alex is curious about data structures. He is working on binary trees recently and particularly interested in complete binary trees.

A complete binary tree satisfies that all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
Alex defines his own complete binary tree: each node has a weight, while father’s is always less than or equal to its sons’. He names this complete binary tree as minimum heap.

Now he wants to know: With N nodes weighted from 1 to N (each appears once), how many heaps can be created. The answer (represented by Q) may be very large, so please output a number P while P = Q mod M.

输入:

The input consists of several test cases. The first line contains a number T, indicating the number of test cases. Each test case is on a single line, and it consists the number N and M.
Technical Specification
1. 1 ≤ T ≤ 10
2. 1 ≤ N ≤ 1000
3. 2 ≤ M ≤ 1000,000,000

输出:

The input consists of several test cases. The first line contains a number T, indicating the number of test cases. Each test case is on a single line, and it consists the number N and M.
Technical Specification
1. 1 ≤ T ≤ 10
2. 1 ≤ N ≤ 1000
3. 2 ≤ M ≤ 1000,000,000

样例输入:

2
1 9973
100 9973

样例输出:

1
174


这个题原来第一次读我以为是数学解决,后来一直想不出来
听说是动态规划才想明白,由于这个题中只有1000个点,所以数组我开的很大
当对一颗子树进行编号的时候,不管是哪些数字,编号方案树都是一样的都是一样的,没有区别,所以对于每一个点,他的方案树就是其两子树的方案数之积 乘以 将其所有子树中节点分到两个子树中的组合数
有了上面的思路之后,最让我头疼的就是二叉树的存储,好吧,我实在想不出来了,就是下面的这个,很笨的方发!
这个题不是动态规划吧,因为这个里面没有决策,我觉得更像递推
贴源码:

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
long long n,m;
int k,s;
long long re;
int sum[1010][1010];//这写数组都可以开小点的
long long dp[1010][1010];

long long c[1010][1010];
//fun c a,b mod m
void initc()//求组合数
{
    int i,j;
    c[0][0] = 1;
    for(i = 1;i < 1010;i++)
    {
        for(j = 0;j <= i;j++)
        {
            c[i][j] = (j == 0) ? c[i-1][j] : ((c[i-1][j] + c[i-1][j-1]) % m);
        }
    }
}
int dfs1(int a,int b)//确定子树中的总点数
{
    sum[a][b] = 0;
    if(a > k) return 0;
    else if(a == k && b > s) return 0;

    dfs1(a+1,b<<1);
    dfs1(a+1,(b<<1)-1);
    sum[a][b] = sum[a+1][b<<1] + sum[a+1][(b<<1)-1] + 1;
    return sum[a][b];
}
long long dfs2(int a,int b)//递推 上面方法可以和这个合为一个,但是当时时间紧没这么做
{
    if(a > k || (a == k && b > s) )
    {
        dp[a][b] = 1;
        return dp[a][b];
    }
    dfs2(a+1,b<<1);
    dfs2(a+1,(b<<1)-1);
    dp[a][b] = (c[sum[a][b] - 1][sum[a+1][b<<1]] *
        ( (dp[a+1][b<<1] * dp[a+1][(b<<1)-1]) % m ))% m;
    return dp[a][b];
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        memset(sum,0,sizeof(sum));
        memset(c,0,sizeof(c));
        cin >> n >> m;
        initc();
        for(int i = 0;i < 1000;i++)
        {
            int tt = 1 << i;
            if(tt-1 > n)
            {
                k = i;
                s = n-((tt>>1) - 1);
                break;
            }
        }//包含k层,最后一层包含s个节点
        //cout << k << " " << s << "\n";
        dfs1(1,1);
        re = dfs2(1,1);
        cout << re << "\n";
    }
    return 0;
}