SRM395 Div2 1000

問題

クイズに何問か答える．各問題について点数pointsが決まっており，i番目の問題に正解するとそのpoints[i]だけ得点がもらえ，不正解だとpoints[i]だけ得点が減る．さらに，正解するとトークンが1つもらえ，tokensNeeded枚たまるとボーナスクイズをすることができる．ボーナスクイズに正解するとbonuses[i]だけ得点がもらえ，トークンはすべて没収される．不正解だとトークンはそのまま維持される．
すべてのクイズの答えを知っている時，もらえる得点を最大化したい．その最大の得点を返す．

考え方

典型DP．
だけど，時間が足りなかったのでメモ化DFSでやった．dfs(現在の得点,現在の問題番号,トークン枚数)．
次の状態遷移は，不正解した場合，正解してトークンがたまってボーナスがもらえる場合，正解してトークンが増える場合の3つ．
メモはdp[トークン枚数][現在の問題番号]=最大得点.