SOSUSOSU

假装这是一个正经的页面

[51nod1086背包问题V2]单调队列优化的多重背包

终于我还是又回来敲代码了(心塞塞

这是两年前只闻其声不见其形的单调队列优化多重背包。。。

二进制背包仿佛也能跑。。。不过我写不来。。。结果单调队列while写成if给wa了几发

本来想摸了直接丢代码。。。后来又想想还是嘴两句吧(弱鸡如我说不定明天就忘了这是怎么写出来的)

首先,如果按01背包大概稳稳t。

然后优化,这个问题和01背包最大的区别是什么?是有很多重复的物品。

于是拿某类物品,一个个的去跑背包,随便一想就知道(并不)会有很多重复的情况,这样更新很亏。

那么怎么优化呢?单调队列啊(废话)!

考虑怎么样的情况可以合并,对于体积为3的物品,体积4(4%3=1)和体积5(5%3=2)的背包显然是不友好的,但是体积4和体积7的背包(%3=1)看起来会舒服得多。

则,令dp[i]=体积为i的背包当前最大价值,那么继续观察,我们若用体积为k的物品更新dp[m],那么大概要去找max{dp[i](i%k==m%k)},这大概就可以用单调队列了吧。

意识流题解写完啦!然后就丢代码跑路啦!

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注