Zombies VS Plants (UVa Live Archive Asia - 2009 Ningbo)
問題
ゾンビを使って5*5のプラントを破壊したい。プラントを壊す方法は2種類ある。1つ目はある行の防御力の合計よりも高い攻撃力の合計を持ったゾンビの軍隊で1行のプラントを全て破壊する方法、2つ目はSpiderを使ってあるプラントを破壊する方法である。行を破壊した時に得られるお金、Sunflowerを破壊した時に得られるお金、初期残金を与えるので最もお金をかけずに全てのプラントを破壊する方法を求めよ。
解法
A*＋枝刈りで解く。まずbool visit[1<<25]をmemsetするとそれだけでTLEするのでbitsetを使うこと。
A*の評価値は「現在までに消費したお金+Magnetが居ないと仮定してFootball playerでプラントを全て破壊するのに掛かるお金」を使う。同じ金額の場合はプラントを壊してる数が多い方を優先する。
枝刈りは以下のような物を使う。
- いずれかの行を全て破壊した物に対してすでに訪れていた場合は無視
- Beanに対してはSpiderを使わない。
- Spiderを使う時にその行を125$以下で壊せる場合は無視
- ゲーム中に得られるお金よりA*の評価値が大きくなったら無視
以上のように頑張って高速化すると間に合う。
