20分求调

P1064 [NOIP2006 提高组] 金明的预算方案

设1和2的主件是0,你的代码里可能出现既选01又选012的情况,这样就重复了,参考 [这篇题解](https://www.luogu.com.cn/article/1qwjd1fe)的第一个分组背包的做法。 你需要改一改你的背包代码 比如: ```cpp for (int i = 1; i <= m; i ++) { if (nd[i].size() == 0) continue; for (int j = n; j >= 0; j --) { for (int k = 0; k < nd[i].size(); k ++) { if (j >= nd[i][k].w) f[j] = max(f[j], f[j - nd[i][k].w] + nd[i][k].v); } } } ``` nd[i]存储了以i为主件的选择方案,这样每个主件的搭配中只选一种方案就不会重复了。
by Hsy122313814 @ 2024-07-30 15:32:52


@[Hsy122313814](/user/555056) 懂了,谢谢大佬
by gyc071116 @ 2024-07-31 08:10:42


|