首页 > 代码库 > DP [HDU 2709] Sumsets

DP [HDU 2709] Sumsets

2024-07-30 03:55:46   216人阅读

Sumsets

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1586    Accepted Submission(s): 609


Problem 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
 弱啊弱啊、弱啊弱
/* 借鉴整数的划分的思想，将j-1变为j/2、可是显然暴搜超时，记忆话二维超内存 *//* #include <iostream>#include <algorithm>#include <cstring>using namespace std;int low(int n){    int k=1;    while(k*2<=n)        k<<=1;    return k;}int q(int i,int j){    if(i==1 || j==1) return 1;    if(i<j) return q(i,low(i));    return q(i,j/2)+q(i-j,j);}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        cout<<q(n,low(n))<<endl;    }    return 0;}*//* 于是看讨论 */// 如果所求的n为奇数，那么所求的分解结果中必含有1，因此，直接将n-1的分拆结果中添加一个1即可 为s[n-1]// 如果所求的n为偶数，那么n的分解结果分两种情况// 1.含有1 这种情况可以直接在n-1的分解结果中添加一个1即可 s[n-1]// 2.不含有1，那么分解因子的都是偶数，将每个分解的因子都除以2，刚好是n/2的分解结果，并且可以与之一一对应，这种情况有 s[n/2]// 所以，状态转移方程为// 如果i为奇数, s[i] = s[i-1]// 如果i为偶数，s[i] = s[i-1] + s[i/2]#include <stdio.h>#define N 1000000#define MOD 1000000000int n,s[N+2];int main(){    s[1]=1;    s[2]=2;    int i=3;    while(i<=N)    {         s[i++]=s[i-1];        s[i++]=(s[i-2]+s[i>>1])%MOD;    }    while(scanf("%d",&n)!=EOF)        printf("%d\n",s[n]);    return 0;}

 

DP [HDU 2709] Sumsets


联系
我们