浅谈一类容量很大但重量很小的背包
覆写
バッドランドに生まれた
只因降生于了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
