POJ 2229 -- Sumsets

http://poj.org/problem?id=2229

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).

http://blog.csdn.net/u014688145/article/details/71091333

递推式：

i 偶数: dp[i] = dp[i/2] + dp[i-1];
i 奇数: dp[i] = dp[i-1];

1
2


1
2

递推思路，i递增后，相当于把所有的1加在了最前方，而当i为奇数时，无法构成新的2的幂，当i为偶数时，能多出一部分解，而多出的那部分解即为dp[i/2]的值。

static int MAX_N = 1000000; static int[] dp = new int[MAX_N+1]; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); dp[0] = 1; for (int i = 1; i <= n;i++){ if ((i & 0x01) == 0){ dp[i] = dp[i/2]; } dp[i] += dp[i-1]; dp[i] %= 1000000000; } System.out.println(dp[n]); in.close(); }
http://www.hankcs.com/program/cpp/poj-2229-sumsets.html
将一个数N分解为2的幂之和共有几种分法？
定义dp[i]为i的分解方案数。dp[0] = 2 ^ 0 = 1，递推到 N 。若i为偶数，则dp[i] = dp[i / 2] + dp[i - 1] + 1，否则dp[i] = dp[i - 1] + 1。

int dp[1000000 + 1]; // 数字i的分解数

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int N;

    cin >> N;

    dp[0] = 1; // 2^0

    for (int i = 1; i <= N; ++i)

    {

        if ((i & 0x1) == 0)

        {

            dp[i] = dp[ i / 2]; // 将i / 2的每个构成数乘以2，得到i

        }

        dp[i] += dp[i - 1]; // 将i - 1的构成数拿过来加一

        dp[i] %= 1000000000;

    }

    cout << dp[N] << endl;

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

http://www.cnblogs.com/kedebug/archive/2012/12/05/2803951.html

1. n为奇数，则肯定其中有1的组成，所以dp[n] = dp[n-1]

2. n为偶数，根据1的存在划分为2种情况：

   a, 有1的组成，则肯定有2个1，dp[n]的一部分是dp[n-2]

   b, 没有1的组成，这时候如果把组成的每个数都除以2，则dp[n]的另一部分就变成dp[n/2]

const int M = 1000000000;
const int MAXN = 1000010;
int dp[MAXN];
int main()
{
    int n;
    scanf("%d", &n);
    dp[0] = dp[1] = 1;

    for (int i = 2; i <= n; ++i)
        if (i & 0x01)
            dp[i] = dp[i-1];
        else
            dp[i] = (dp[i-2] + dp[i>>1]) % M;

    printf("%d\n", dp[n]);
    return 0;
}

Read full article from 2229 -- Sumsets