51nod 1011 【完全背包】

完全背包的变形；

这些数字可以取多次，dp[i]代表前 i 物品组成N时的方案数。

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdio>

#include<map>

#include<vector>

#include<queue>

using namespace std;

typedef long long LL;

const int mod=1e9+7;

int w[13]={1,2,5,10,20,50,100,200,500,1000,2000,5000,10000};

LL dp[100010];

void init()

{

    dp[0]=1;

    for(int i=0;i<13;i++)

    {

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

        {

            if(dp[j-w[i]])

                dp[j]=(dp[j]+dp[j-w[i]])%mod;

        }

    }

}

int main()

{

    init();

    int n;

    scanf("%d",&n);

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

    return 0;

}

巴特西

51nod 1011 【完全背包】

最新文章

热门文章