KUPC2012 D.権力
問題
N個の部屋が1直線上に並んでおり、外からの侵略者が各部屋を狙っている。
侵略者から部屋を守りたい。
ある人は、ある区間をまとめて守ることができ、人と守れる区間のリストが与えられる。
できるだけ少ない人数で守る時、その人数を答える。
全ての部屋を守れないときはImpossibleを返す。
考え方
各部屋をノードと考えて、ある区間i〜jを守る時、iからi+1、iからi+2、、、iからj、iからj+1までコスト1の辺をはる。
1の部屋から(仮想的な)N+1の部屋まで最小コストで移動したものが、答えになる。
反省
1をカバーできるもので、一番広くカバーできるものを選ぶ。
カバーできてない範囲で一番小さい番号の部屋をカバーできるもので、一番広くカバーできるものを選ぶ。
上記を繰り返す貪欲法で解ける。