淺談一類容量很大但重量很小的背包——2025.7.27 鮮花
淺談一類容量很大但重量很小的背包
覆寫
バッドランドに生まれた
只因降生于了bad land【惡劣環境】
だけでバッドライフがデフォとか
就default【默認】了必然承受bad life【痛苦生命】
くだらないけど、それが理なんだって
雖然這種理論很無聊,但它卻已成當然
もう參っちゃうね
已經受不了了
抗うために
為了對抗它
エスケープ?フロム?デンエン
我escape from denen【逃離鄉間】
蛇のように這い、善戦
如蛇般爬行,驍勇善戰
だけど最後、逆転の一手だけ
但最后卻只是,僅剩致勝一招
何故か詰められないの!
卻不知為何無法再繼續下去!
暗い無頼社會 vs. BRIGHT未來世界
如果將黑暗的無聊社會 與BRIGHT【明亮】的未來世界作對比
ならちょっと後者に行ってくる
那我還是先行一步向著后者去吧
大丈夫か?うるせえよ
這樣沒問題嗎?可真煩人啊
限界まで足掻いた人生は
已然到達界限的人生啊
想像よりも狂っているらしい
似乎比想象中的還要瘋狂幾分
半端な生命の関數を
就讓我在這一帶稍許
少々ここらでオーバーライド
override【覆寫】一下我那廢物般的人生函數吧
…したい所だけど現実は
…雖然想這么做但現實卻似乎
そうそう上手くはいかないようで
常常不如想象般的那樣美好
吐いた言葉だけが信條だって
只有傾吐的話語才能作為信條
思われてまた離れ離れ
人們如此想著又再次相互分離
まぁ、この世の中ガチャの引き次第で
嘛,這個世界的抽卡結果
何もかも説明つくわけだし?
不就早已說明了一切嘛?
巻き返しに必要な力で
那么把卷土重來的氣力
別の事頑張ればいいじゃん(笑)
轉到別的事上去干不就行了(笑)
まぁ、この地獄の沙汰も金次第で
嘛,「有錢能使鬼推磨」這個道理
どこまでも左右出來るわけだし?
不早已左右了一切事物嗎?
アンタが抜け出せるわけがないよ(笑)
你也逃不出這一定律哦(笑)
それで話はおしまい?
所以話說完了吧?
ならば もう こないからねー
那么 已經 不會再來了呢—
豪快さにかまけた人生は
沉溺于豁達大度的人生啊
きっと燃やされてしまうらしい
似乎最終一定會被燃燒成灰
じゃあワタシなど要らないと
那么「我等無用」 之類的
蹴った果てにいた付和雷同
在憤然盡頭產生的隨聲附和
シタイだけ探した冒険TONGUE
這種找尋到的結果至上的冒險TONGUE【風格】
どうか消えるまでスタンド?バイ?ミー
還請直到消失都stand?by?me【與?我?一?起】
撒いたエラーすら読んじゃいない
就連散布的error【錯誤】都無法解讀
人間の思う事は知らないね!
理解不了人類的所思所想啦!
アンタが書いた杜撰なコード
你所寫下的粗糙chord / code【和弦 / 代碼 / 規則】
ばっか持てはやすユーザーよ
只會受到傻子user【用戶】的歡呼擁護
吐いた言葉の裏なんて
那么傾吐的話語的深層含義
知る由もないだろう
也就不得而知了吧
哀れ、あはれ。
何其悲哀。

寫這個的原因是被 ABC 的一個題創了。
都被出爛了。
我們先貪心填,這里我們只需要將剩余容量填到一個可以接受的程度即可。
設容量是 \(V\),重量是 \(W\)。
結論:
一定存在一個到達最優解的方案使得當前容量 \(V'\) 始終滿足 \(V - W \le V' \le V + W\)。
所以其背包容量可以放縮在 \(V \pm {\cal O}(D^2)\),物品個數也不會超過 \({\cal O}(D^2)\)。
考慮一些特殊問題的特化:
-
完全背包
這個問題有經典的同余最短路解法:同余最短路的轉圈技巧——Alex_Wei。
容易發現其復雜度是 \({\cal O} (\max\{m^2 + nm\})\)。
這個做法復雜度是很優秀的,但是不太能處理一些特殊的限制。但是直接做會將其轉化為多重背包,不太好寫。
我們發現對于完全背包的貪心異常簡單,甚至可以先 \(dp\) 再貪心,于是就做完了。
這個復雜度是 \(nm^2\) 的,很不好。
-
01 背包判定:
直接參考 鮮花 中 ABC221G 的部分即可。
-
多重背包判定:
轉成 01 背包即可做更好的復雜度,好像是不太能去掉 \(\log\),我不會。
P





本文來自博客園,作者:xrlong,轉載請注明原文鏈接:http://www.rzrgm.cn/xrlong/p/19006956
版權聲明:本作品采用 「署名-非商業性使用-相同方式共享 4.0 國際」許可協議(CC BY-NC-SA 4.0) 進行許可。

浙公網安備 33010602011771號