原题链接 Sumsets Time Limit: 2000MS Memory Limit: 200000K Total Submissions: 17986 Accepted: 7052 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
7 Sample Output
6 Source
USACO 2005 January Silver
#include <cstdio>#include <iostream>using namespace std;const int maxn = 1000000 + 10;long long dp[maxn];int main(){ int n; cin >> n; dp[1]=1; for(int i=2;i<=n;i++){ if(i&1) dp[i]=dp[i-1]; else dp[i] = (dp[i/2] + dp[i-1])%1000000000; cout << i << ":" << dp[i] << endl; } cout << dp[n] << endl; return 0;}/*下面是完全背包的做法#include <cstdio>#include <iostream>using namespace std;const int maxn = 1000000 + 10;const int mod=1e9;int dp[maxn];int main(){ int n; cin >> n; dp[0]=1; for(int i=1;i<21;i++){ int v=(1<<(i-1)); for(int j=v;j<=n;j++){ dp[j] = dp[j] + dp[j-v]; while(dp[j]>mod) dp[j]-=mod; } } cout << dp[n] << endl;}// i 0 1 2 3 4 5// v[i] 1 2 4 8 16 32// i/j 0 1 2 3 4 5 6 7// 0 0 0 0 0 0 0 0 0 i:1~ceiling j:v[i-1]~n// 1 1 1 1 1 1 1 1 1 dp[j] = dp[j] + dp[j-v[i-1]]; v[i-1]<= j <=n;// 2 1 1 2 2 3 3 4 4 // 3 1 1 2 2 4 4 6 6// 4 1 1 2 2 4 4 6 6*/新闻热点
疑难解答
