AOJ DPL_1_I

数ヶ月前、蟻本片手に AOJ の組合せ最適化問題を解いていた際、以下の問題に遭遇した。

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_I

 

制約条件的にナイーブな dp は使えなさそうだと思いつつ、結局いい感じの解法が思いつかなかったので他の方の solution を拝見したところ、以下の 2 つの方針がありそうだった。

  1. dp 使ってある程度解を求めた後で greedy に最終的な解を求める
  2. 枝刈りありの深さ優先探索 (正式名は "分枝限定法" ?) で解を出す

方針 1 の実装で厳密解求まるかどうかが判断出来なかったので、方針 2 を実装して submit し、そのときはそのまま何も考えず終わりにしてしまった。

最近になってふと方針 1 についても色々考えたり調べたりしてみたが、何故この解法で OK なのか未だに良くわかっていない。アルゴリズム力が足りない (悲しい)。

 

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?