题目大意

给定一个数N，问由不同的2的幂之和能组成N的方法有多少种

题解

看完题目立马想到完全背包。。。敲完代码上去超时了。。。。后来发现是%的原因。。。改成减法就A了。。。%也太他妈耗时了吧！！！（还有一种O(n)的算法。。。）

代码：

#include<stdio.h>

#include<string.h>

#define MOD 1000000000

#define MAXN 1000005

int dp[MAXN];

int main()

{

    int n;

    scanf("%d",&n);

    memset(dp,0,sizeof(dp));

    dp[0]=1;

    for(int i=1; i<=n; i<<=1)

        for(int j=i; j<=n; j++)

        {

            dp[j]+=dp[j-i];

            if(dp[j]>=MOD)

                dp[j]-=MOD;

        }

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

    return 0;

}

巴特西

POJ2229 - Sumsets（完全背包）

题目大意

题解

代码：

最新文章

热门文章