POJ 2229 Sumsets————（完全背包 or 规律）

男娘i 2022-05-18 04:36 162阅读 0赞

**Sumsets**  
Time Limit: 2000MS Memory Limit: 200000K  
Total Submissions: 23184 Accepted: 8888  
**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

--------------------

将一个数划分成2的幂之和，一共有多少种划分方式  
1 完全背包的思想  
2 找规律

--------------------

1.完全背包

/*
        利用完全背包的思想来解决 
    */
    #include<cstdio> 
    #include<cstring>
    using namespace std;
    const int MAXN=1e7+7;
    const int mod=1e9;
    int c[30];
    int dp[MAXN];
    int n,m;
    
    int main() 
    {
        int m=1;
        c[1]=1;
        while(1)
        {
            m++;
            c[m]=c[m-1]*2;
            if(c[m]>MAXN)   break;
        }
        while(~scanf("%d",&n))
        {
            memset(dp,0,sizeof(dp));
            dp[0]=1;
            for(int i=1;i<m;i++)
            {
                if(c[i]>n)  break;
                for(int j=c[i];j<=n;j++)
                {
                    dp[j]+=dp[j-c[i]];;
                    if(dp[j]>mod)   dp[j]%=mod;
                }
            }       
            printf("%d\n",dp[n]);
        }
        return 0;
    }

#include<cstdio>
    using namespace std;
    const int mod=1e9;
    const int MAXN=1e7+7;
    int f[MAXN];
    
    int main() 
    {
        f[0]=1;
        f[1]=1;
        for(int i=2;i<MAXN;i++)
            if(i&1) f[i]=f[i-1];
            else    f[i]=f[i-1]%mod+f[i>>1]%mod;
    
        int n;
        while(~scanf("%d",&n)) 
            printf("%d\n",f[n]%mod);
        return 0;
    }

--------------------

有的地方我也不很理解，先记录下来，回头在仔细理解