Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

08/20
19:11
背包动规

[bzoj 1677] Usaco2008Jan Sumsets 求和

20131208173503_QxZGW   32fa828ba61ea8d3abec1bb0950a304e241f58b3

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 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 .给出一个N,使用一些2的若干次幂的数相加来求之.问有多少种方法

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

 一个整数N.

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

 方法数.这个数可能很大,请输出其在十进制下的最后9位.

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

7

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

6

有以下六种方式
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

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

(1N10^6)

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

完全背包,第i个背包的重量是2^(i-1)

做logn次转移,第i次转移f[j]表示用前i个去组成j的方案数,边界f[0]=1

c++:

pascal:

20140321165052_zPdxm.thumb.700_0

 

[bzoj 1677] Usaco2008Jan Sumsets 求和