次の問題を解いた。
yukicoder No.783 - 門松計画
この問題の解説を見ることで、個数制限なしナップサックDPを使えるようになった。個数制限なしナップサックDPについて少し勘違いしていて、次の順序でDPをするものだと思っていた。
- 荷物1を可能な限り追加する
- 荷物2を可能な限り追加する
- 以下荷物Nまで続く
しかし、次の順序でも行うことができる。
- 重さの合計0に荷物1～Nを追加する
- 重さの合計1に荷物1～Nを追加する
- 以下重さの上限まで続く
どちらも計算量は同じ。
後者の順序が優れている点は、荷物の入れる順序をDPの状態として持てる点。
たとえば「荷物1の後には荷物2を入れたくない」みたいなときに、前者の順序では対応できないが、後者の順序なら状態として「前回入れた荷物の番号」を持てば対応できる。今回の問題に対応できるのも後者。
2つの順序の見分け方は簡単で、一番外側のループが荷物か重さかで見分けられる。
終わりに
今回の問題では個数制限なしナップサックDPを使えないと思ったので、計算量O(N5)くらいのコードを提出した。それでも通ってしまったので制約もしくはテストは若干甘め。
