poj 2229 【完全背包dp】【递推dp】

Sumsets

Time Limit: 2000MS		Memory Limit: 200000K
Total Submissions: 21281		Accepted: 8281

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

Sample Output

Source

USACO 2005 January Silver

题意：用2的幂次（1，2，4，8...)表示N，有多少种表示方法。

题解：

【完全背包】：

　　定义：dp[i][j]表示前i个2的幂表示j有多少种方法，则dp[i][j]=Σ{dp[i-1][j-k*c[i]]|0<k*c[i]<=N}

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn=1e6;
 8 const int mod=1e9;
 9 
10 int f[maxn];
11 
12 int main()
13 {
14     int N,M;
15 
16     while(scanf("%d",&N)==1)
17     {
18         memset(f,0,sizeof(f)),f[0]=1;
19         for(int i=1;; i++)
20         {
21             int t=(1<<(i-1));
22             if(t>N) break;
23             for(int j=t; j<=N; j++)
24             {
25                 f[j]+=f[j-t];
26                 while(f[j]>mod) f[j]-=mod;
27             }
28         }
29         printf("%d
",f[N]);
30     }
31     return 0;
32 }

【递推dp】：

　　定义：dp[N]表示答案。当N为奇数时，dp[N]=dp[N-1];当N为偶数时，若组成N的数中没有1，则把这些数除以2，就是dp[N/2]；若有1（显然有1就至少有两个1)，则去掉两个1，相当于是dp[N-2].所以dp[N]=dp[N/2]+dp[N-2]

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 1e6;
 7 const int mod = 1e9;
 8 
 9 int dp[maxn];
10 
11 int main()
12 {
13     int n;
14     cin >> n;
15     memset(dp, 0, sizeof(dp));
16     dp[1] = 1, dp[2] = 2, dp[3] = 2, dp[4] = 4;
17     for (int i = 4; i <= n; i++) {
18         if (i % 2 == 1) dp[i] = dp[i - 1]%mod;
19         else dp[i] = (dp[i - 2] + dp[i / 2]) % mod;
20     }
21     cout << dp[n] << endl;
22     return 0;
23 }

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6;
const int mod=1e9;

int dp[maxn+100];

int dfs(int n)
{
    if(dp[n]>0) return dp[n];
    if(n%2==1)
        return dp[n]=dfs(n-1)%mod;
    else
        return dp[n]=(dfs(n-2)+dfs(n/2))%mod;
}

int main()
{
    memset(dp,0,sizeof(dp));
    int n;
    dp[1]=1,dp[2]=2,dp[3]=2,dp[4]=4;
    while(scanf("%d",&n)==1)
    {
        printf("%d
",dfs(n));
    }
    return 0;
}