首页 > ACM题库 > HDU-杭电 > hdu 2085 核反应堆-动态规划-[解题报告]C++
2013
12-29

hdu 2085 核反应堆-动态规划-[解题报告]C++

核反应堆

问题描述 :

某核反应堆有两类事件发生:
高能质点碰击核子时,质点被吸收,放出3个高能质点和1个低能质点;
低能质点碰击核子时,质点被吸收,放出2个高能质点和1个低能质点。
假定开始的时候(0微秒)只有一个高能质点射入核反应堆,每一微秒引起一个事件发生(对于一个事件,当前存在的所有质点都会撞击核子),试确定n微秒时高能质点和低能质点的数目。

输入:

输入含有一些整数n(0≤n≤33),以微秒为单位,若n为-1表示处理结束。

输出:

输入含有一些整数n(0≤n≤33),以微秒为单位,若n为-1表示处理结束。

样例输入:

5 2
-1

样例输出:

571, 209
11, 4



提示
可以使用long long int对付GNU C++,使用__int64对付VC6

2011-12-15 04:37:17

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2085

题意:中文。裸递推。

代码:

# include <stdio.h>


long long dp[40][2] = {1, 0} ;


int main ()
{
    int i, n ;
    for (i = 1 ; i<= 33 ; i++)
    {
        dp[i][0] = dp[i-1][0]*3 + dp[i-1][1]*2 ;
        dp[i][1] = dp[i-1][0] + dp[i-1][1] ;
    }
    
    while (~scanf ("%d", &n) && n != -1)
        printf ("%I64d, %I64d\n", dp[n][0], dp[n][1]) ;

    return 0 ;
}

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/01/06/2314694.html


  1. “可以发现,树将是满二叉树,”这句话不对吧,构造的树应该是“完全二叉树”,而非“满二叉树”。