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

(o_o)

ブログ。

AOJ1353 Sweet War

問題概要
1つのチョコボールのスタックを使って2人ゲームを行う.
それぞれのチョコボールに栄養価r_iと美味しさs_iが定められており,
2人は食べたチョコボールの美味しさを最大化したいと考えている.

2人にはそれぞれ体力値が定められており,それぞれ初期値はA,Bである.
交互に以下の行動のうちのいずれかを行う.
パス:チョコボールを食べない.体力が1減る.残り体力が0のときはパスできない.
食べる:スタックの一番上のチョコボールを食べる.体力がr_i上がる.
スタックが空になったときゲーム終了である.

双方が最適な行動をとった場合,それぞれが食べる美味しさの和を求めよ.

解法
反射的に思いつくのは
dp[i][j] = 体力差がjあるときに,i番目のチョコ以降で付けられる点差の最大値
みたいな感じのDPだけど,これだと O(N^2 * (A+B)) でダメ.
そこで,これを
dp[i][j] = i番目のチョコ以降で j 点差以上つけるのに必要な体力差の最小値
みたいな感じに変形する.蟻本にもあるテクだよね.

パスする場合と食べる場合の2通りの行動パターンがある.
ここで,r_i >= 0 であるから,自分の方が体力差が1以上強い場合はパスすることで相手に手番を渡せて,
そうでないときはパスが効かないことがちょっと考えたらわかる.
食べる場合がちょっと複雑で,相手にとってj点差あるときは体力差が dp(i,j) あれば相手が勝ってしまうから,
体力差が dp(i,j)+1 あれば相手は高々 j-1 点差しかつけられないよね・・・みたいな感じで適宜 +1 や -1 を補った DP 式を書かなきゃいけない.そこらへんは実装に依りそう.

DPは苦手.っていうか再帰が苦手や



gist5308780ac37a5d7b96c9