Sumsets

直接翻译了

Descriptions

Farmer John 让奶牛们找一些数加起来等于一个给出的数N。但是奶牛们只会用2的整数幂。下面是凑出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

帮助FJ找到 N的分配数 (1 <= N <= 1,000,000).

Input

Output

排列方式总数。由于这个数可能很大，只需要保留最后9位

Sample Input

Sample Output

Hint

打表的会被系统自动识别判为WA

题目链接

https://vjudge.net/problem/POJ-2229

处理出2的幂次方的所有的数字，当做物品，每个物品次数不限，求凑出体积为N的方案数

类似完全背包，先枚举物品，再正序枚举体积，转移状态dp[i][j]表示前i件物品凑出的体积为j的方案数

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - w[i]]

1<<i 相当于 2ⁱ

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 1000005

using namespace std;

int n;

int w[Maxn];

int cnt=;

int dp[Maxn];

int main()

{

    scanf("%d",&n);

    for(int i=;(<<i)<=n;i++)//构造所有物品

        w[cnt++]=(<<i);

    dp[]=;

    for(int i=;i<cnt;i++)

        for(int j=w[i];j<=n;j++)

            dp[j]=(dp[j]+dp[j-w[i]])%;//取余

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

    return ;

}

巴特西

【POJ - 2229】Sumsets（完全背包）

Sumsets

最新文章

热门文章