読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2296 Quest of Merchant

頑張るだけ

解法

色々眺めていくとナップサック以外考えられなくなると思うのでナップサックで考える.
まず初めの考察として,原点から出発して再び原点に返ってくる操作を1セットとできそう.

では1セットにしてどうするか.どう見てもN \le 7が怪しい.
1セットで訪れる町の集合を個別に考える.町の集合は2^N通り.
訪れる町の集合が決まると,その町の集合を全部通って原点に帰るまでの最短時間はTSPもどきでまとめてN2^Nで求められる.
また,町の集合ごとに取得できる商品についてナップサックDPを行うことで,1セット(重量上限W)で持ち帰れる最大の商品価値をNM+MWで求めることができる.

つまりここまでで,各訪れる町の集合ごとに,(所要時間t,商品の合計価値v)という情報が得られる.
あとはこれを使ってナップサックDPを行い,時間T以内に取得できる商品価値の最大値を求めてやればよい.