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