Sumsets
| Time Limit: 2000MS | Memory Limit: 200000K | |
| Total Submissions: 19024 | Accepted: 7431 |
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
——————————————————————————————————
题目的意思是给出一个数问把他变成若干个2^x的数累加，问有多少种不同情况
思路：方法一：dp，完全背包 +打表
方法二：分析可知对于第i项，i为奇数项就等于i-1项的值，i为偶数项就等于i-1项 加上i/2项的值（把i/2项每个数*2）
方法一：可能会超时，看判题机状态
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits> using namespace std; #define LL long long
const int INF = 0x3f3f3f3f;
const int mod=1000000000;
int dp[1000005]; int main()
{
int n;
memset(dp,0,sizeof dp);
dp[0]=1;
for(int i=0;i<=20;i++)
{
int k=pow(2,i);
for(int j=k;j<1000005;j++)
{
dp[j]=(dp[j]+dp[j-k])%mod;
}
}
while(~scanf("%d",&n)){
printf("%d\n",dp[n]); } return 0;
}
方法二：效率较高
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits> using namespace std; #define LL long long
const int INF = 0x3f3f3f3f;
const int mod=1000000000;
int dp[1000005]; int main()
{
int n;
memset(dp,0,sizeof dp);
dp[1]=1;
for(int j=2;j<1000005;j++)
{
if(j%2)
dp[j]=dp[j-1]%mod;
else
dp[j]=(dp[j-1]+dp[j/2])%mod;
}
while(~scanf("%d",&n)){
printf("%d\n",dp[n]); } return 0;
}