前段時(shí)間遇到個(gè)完全背包問(wèn)題,于是看了DD牛的背包九講，對(duì)于01背包和完全背包還好理解，不過(guò)對(duì)于多重背包我一直理解的不是很透徹，尤其是那個(gè)復(fù)雜度,我一直認(rèn)為是O(N*V*Σ(log(n[i])))的，但是DD牛的九講上說(shuō)是O(V*Σ(log(n[i]))，這個(gè)復(fù)雜度確實(shí)是DD牛講的那個(gè),表示一開(kāi)始我想錯(cuò)了。還有就是可以用單調(diào)隊(duì)列優(yōu)化達(dá)到O(N*V),于是上網(wǎng)搜了好多報(bào)告,無(wú)奈實(shí)在不懂。后來(lái)問(wèn)了王向，他說(shuō)不用單調(diào)隊(duì)列也可以達(dá)到O(N*V)的,給了我個(gè)網(wǎng)址。昨天下午就學(xué)些了下。發(fā)現(xiàn)還比較好懂。今天上午就依著那個(gè)思路把1014和1742給寫(xiě)了，發(fā)現(xiàn)還可以速度不錯(cuò)。
附上1014的帶注釋代碼