Sumsets
Time Limit: 2000MS | Memory Limit: 200000K | |
Total Submissions: 11009 | Accepted: 4433 |
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
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).
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
7
Sample Output
6
说实话我觉得这道题不应该算动态规划,难道分类到动规的原因是递推公式和记忆化,那好吧。。。
设数字n的表示形式有f(n)种,递推公式就是:
f(n)=f(n-1) (n为奇数)
f(n)=f(n/2)+f(n-1) (n为偶数)
因为只能用2^i表示,所以奇数必然要有1,1后面的表示方法数就是f(n-1)了,所以n为奇数时就是f(n)=f(n-1)
而偶数时要分类计论,表示中含有1的和不含有1的,含有1的就是f(n-1),不含有1的就是f(n/2),所以n为偶数时就是上f(n)=f(n-1)+f(n/2)
1 #include<iostream> 2 #include<cstdio> 3 4 using namespace std; 5 6 const int mod=1000000000; 7 8 long long dp[1000010]; 9 10 int main() 11 { 12 int n; 13 14 dp[1]=1; 15 for(int i=2;i<=1000000;i++) 16 if(i%2) 17 dp[i]=dp[i-1]; 18 else 19 dp[i]=(dp[i-1]+dp[i/2])%mod; 20 21 while(scanf("%d",&n)==1) 22 cout<<dp[n]<<endl; 23 24 return 0; 25 }