POJ-2229

题目

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 (1 <= N <= 1,000,000).

Input

A single line with a single integer, N.

Output

The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).

Sample Input

1
7

Sample Output

1
6

思路&心得

  • DP问题,先讨论下起始情况:当n = 1的时候,只有1种;当n = 2的时候,有两种;
  • 当n为奇数时,将n - 1的所有情形都加上1即可以得到n时的个数。dp[n] = dp[n - 1];
  • 当n为偶数时,又分为两种情况:若式子含有1,则这种情况的个数为dp[n - 1];若式子不包含1,即全都是偶数,则将所有加数都除以2,可得到个数为dp[n / 2]的值;
  • 题目中要求的输出为实际值的最后九位数字,所以每次计算时要对1000000000取模。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
const int MAX_N = 1000005;
const int mod = 1000000000;

int dp[MAX_N];

int f(int n) {
for (int i = 3; i <= n; i ++) {
if (i & 1) dp[i] = dp[i - 1];
else dp[i] = (dp[i - 1] + dp[i / 2] ) % mod;
}
return dp[n];
}

int main() {
int N;
dp[1] = 1, dp[2] = 2;
while (~scanf("%d", &N)) {
printf("%d\n", f(N));
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×