首页 > ACM题库 > HDU-杭电 > hdu 2709 Sumsets-动态规划-[解题报告]C++
2014
02-14

hdu 2709 Sumsets-动态规划-[解题报告]C++

Sumsets

问题描述 :

Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:

1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).

输入:

A single line with a single integer, N.

输出:

A single line with a single integer, N.

样例输入:

7

样例输出:

6

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

题意:一个整数n,表示为若干个2的幂的数字和,问有多少种(mod 1e9)。

mark:递推题,考虑1的个数不同,剩下的都是2的幂,可以除以2转移成更小的状态。得递推方程为dp[i] = dp[i-2] + dp[i/2]。注意初始值。

代码:

# include <stdio.h>
 
 
 int tab[1000010] = {1, 1, 2} ;
 
 
 int main ()
 {
     int i ;
     for (i = 3 ; i <= 1000000 ; i++)
         tab[i] = (tab[i-2] + tab[i/2] ) % 1000000000 ;
     while (~scanf ("%d", &i))
         printf ("%d\n", tab[i]) ;
     return 0 ;
 }

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


  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

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