オンサイトで未確認

ukuku09の活動記録。

AOJ 0274: Arts and Crafts

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?lang=jp&id=0274

 

解法

bitDP + 最小費用流。

むかし見たときは全然わからなかったけど、昨日やったら解けたのでわーい!すっごーい!(は?

 

まず bitDP パートから。問題文に、

  • それぞれの課題について、1回の授業でL個までの部品を購入することができる。
  • 部品を使用する順序は課題の完成に影響を与えない

と書いてあるので、D 回の授業である部品の集合を購入する最小価格を求める。順序がないので最適な買い方は部品の日ごとの費用だけで決まる。また、部品の種類はたかだか 8 種類、課題ごとに使用する同じ部品の数は最大 2 個なので、16bit の bit 列で表現できる。結局、dp[i][j][S] := i 回目の授業で j 個買ったときに S となる最小価格となる( i, j の部分の配列は使いまわせる)。

 

最小費用流パートは、課題と袋をノードにして流量 N を流すだけ。課題と袋のほかに、すべての課題とつながるソースと、すべての袋とつながるシンクを作っておく。あとは

  • 教員は、児童1人につき袋を1つだけ渡すことができる(袋を渡さない児童がいてもよい)。
  • 袋を渡された児童は、袋の中に入っている部品をすべて、自分が制作する課題に使わなければならない。

というところに気をつけて、課題と袋の間に先ほどの DP で求めた価格の辺を張る。