关于我哪里写错了
查看原帖
关于我哪里写错了
602932
NumberTrart楼主2023/1/2 14:57

计数型多重背包,不就是这么写吗

#include<cstdio>
#include<iostream>
using namespace std;
const int P=1e6+7;
int n,m,a;
int cnt,w[705],dp[105];
#if 0
额,这个注释风格你别管
总之,明确一下
计数型多重背包
m是背包容量
n是“物品”种数
cnt是物品堆个数
w[]是物品体积
#endif
int main()
{
    cin>>n>>m;
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        for(int j=1;j<=a;j*=2)
        {
            w[++cnt]=j;
            a-=j;
        }
        if(a>0)
            w[++cnt]=a;
    }
    for(int i=1;i<=cnt;i++)
        for(int j=m;j>=w[i];j--)
        {
            dp[j]+=dp[j-w[i]];
            dp[j]%=P;
        }
    cout<<dp[m];
    return 0;
}

全wa了

2023/1/2 14:57
加载中...