9/2 PKU
1717 Dominoes
1000個以下のドミノがあって、横に並んでる。何個かひっくり返して上下の数の和の差を最小にしたい。最低何個ひっくり返せばいい?
DPやるだけ
3041 Asteroids
危険な小惑星があるらしい。それをスターライトブレイカーかレールガンか知らないけどぶち壊すらしい。スターライトブレイカーで一行か一列にあるものを1回に破壊できる。最低何回撃つ必要がある?
行、列をノードとして、小惑星があるならその小惑星の行、列の間に辺を張る。そして最大マッチング。何故かしらないがこれで解ける。
2226 Muddy Fields
Asteroidsにすごいよく似てる。
泥地と草地があって、泥地にパッチを貼りたい。パッチは幅1の長方形。パッチは草地にかかってはいけない。泥地を全部覆うためにパッチはいくつ必要?
縦だけで見て、連続した部分には同じ縦idを与える。横についても同様。そして縦id->横idで最大マッチング。