首页 > ACM题库 > HDU-杭电 > hdu 2502 月之数-动态规划-[解题报告]C++
2014
02-09

hdu 2502 月之数-动态规划-[解题报告]C++

月之数

问题描述 :

当寒月还在读大一的时候,他在一本武林秘籍中(据后来考证,估计是计算机基础,狂汗-ing),发现了神奇的二进制数。
如果一个正整数m表示成二进制,它的位数为n(不包含前导0),寒月称它为一个n二进制数。所有的n二进制数中,1的总个数被称为n对应的月之数。
例如,3二进制数总共有4个,分别是4(100)、5(101)、6(110)、7(111),他们中1的个数一共是1+2+2+3=8,所以3对应的月之数就是8。

输入:

给你一个整数T,表示输入数据的组数,接下来有T行,每行包含一个正整数 n(1<=n<=20)。

输出:

给你一个整数T,表示输入数据的组数,接下来有T行,每行包含一个正整数 n(1<=n<=20)。

样例输入:

3
1
2
3

样例输出:

1
3
8

2011-12-15 03:44:22

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

题意:中文。。。

mark:应该有公式,不过直接递推吧。。。dp[i]表示所有长度小于等于i的数共有多少个1。

代码:

# include <stdio.h>
# include <stdlib.h>


int dp[25] = {0, 1} ;


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

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


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  3. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  5. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.