POJ 1742 Coins——不要套单调队列优化多重背包的模板

POJ 1742 Coins——不要套单调队列优化多重背包的模板

和HDU 2844一模一样，但是这个题的测试数据很变态，对时间和空间的要求都很高，被称为男人八题......

一开始定义dp[i]为最大价值，然后套上了多重背包模板，超时；

然后优化了一下，套上了单调队列优化多重背包模板，还是超时；

这时就感觉不能定义dp[j]为最大价值，应该把dp[j]定义成数量一类的东西，并把多重背包模板变一下形；

因此定义dp[j]为到达体积j当前面值的硬币至少用多少枚，此时要满足dp[j - v[i]] + <= n[i],并用vis数组记录哪些体积是可以达到的，最后遍历一遍vis即可，这样就省去了一层循环。

#include #include using namespace std;const int maxn = 100000 + 10;int N, V, n[110], v[110], dp[maxn], vis[maxn];int main() { while (scanf("%d %d", &N, &V) == 2 && N + V) { for (int i = 1; i <= N; i++) scanf("%d", &v[i]); for (int i = 1; i <= N; i++) scanf("%d", &n[i]); memset(vis, 0, sizeof(vis)); vis[0] = 1; for (int i = 1; i <= N; i++) { memset(dp, 0, sizeof(dp)); for (int j = v[i]; j <= V; j++) { if (vis[j]) continue; if (vis[j - v[i]] && dp[j - v[i]] < n[i]) { dp[j] = dp[j - v[i]] + 1; vis[j] = 1; } } } int ans = 0; for (int i = 1; i <= V; i++) { if (vis[i]) ans++; } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。