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は苦手．っていうか再帰が苦手や
