POJ 2229 Sunsets (动态规划)

Description

给出一个正整数N，用多个2的整数幂之和表示出来，求共有几种方案

Analyze

像完全背包，只不过这里要求方案数

dp[i][j] 表示安排前n个物品到容量为m的背包中的方案数

dp[i][j] = dp[i - 1][j] + dp[i][ j - w[i] ] （01背包中 + dp[i - 1][j - w[i] ]）

1. 将前(i - 1)个物品安排到 j 容量的背包方案数（不放第i个物品了）
2. 将前 i 个物品安排到(j - w[i])容量的背包方案数（第i个物品再放一个进去）

然后按照顺序可以省去第一维

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000005;

int w[N], dp[N];

int main()
{
    int n, tot = 0;
    scanf("%d", &n);
    for(int i = 0; (1 << i) <= n; ++i)
        w[tot++] = (1 << i);
    dp[0] = 1;
    for(int i = 0; i < tot; ++i)
        for(int j = w[i]; j <= n; ++j)
            dp[j] = (dp[j] + dp[j - w[i]]) % 1000000000;
    cout << dp[n] << '\n';
    return 0;
}