题目内容

P1077

大意:现要摆 m 盆花,一共 n 种花,从种类编号小到大摆,每种花最多摆 a_i 盆,求方案数

解题思路

此题抽象出来后可看作多重背包问题求方案数,每盆花的价值是 1,求装满 m 的方案数。

#include <cstdio>

const int p=1000007;
int n,m,f[105],w[1005];

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    scanf("%d %d",&n,&m);
    int x;
    for(int i=1;i<=n;i++)
        scanf("%d",w+i);
    f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=1;k<=min(w[i],j);k++)//枚举这种花的数量
                f[j]=(f[j]%p+f[j-k]%p)%p;
    printf("%d\n",f[m]);
    return 0;
}
最后修改日期:2020年3月11日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。