2020-07-20 19:55
동명대학교 算法工程师 Clouder0:种类较多可以考虑用背包的思路来解,对每种面值跑分组背包。复杂度大概为$O(nm^2)$,$n$为物品种数,$m$为值域。
```cpp
const int maxn = 10000;
const int maxm = 510;
int n,m;
int f[maxm],w[maxn];
int main()
{
read(n),read(m);//nm^2
for(int i = 1;i<=n;++i) read(w[i]);
f[0] = 1;
for(int k = 1;k<=n;++k)
for(int i = m;i;--i)
for(int j = i / w[k];j;--j)
f[i] += f[i - j * w[k]];
printf("%d\n",f[m]);
return 0;
}
```
0 点赞 评论 收藏
分享
创作者周榜
更多
关注他的用户也关注了: