SRM602 Div1E

・SRM602 Div1E TypoCoderDiv1

整数xをもっていて,xに対しn回操作を行う.i回目の操作ではxにD[i]を足すかxからD[i]を引くか選べる(ただし結果が0以下になるときは0とする).xが2200未満から2200以上になるとき,xが2200以上から2200未満になるとき(つまり2200のラインをまたぐとき)1回と数えると最大で何回またぐことができるか.ただしある操作でxが2200以上になったとき,それが最後の操作でないときは次の操作で2200未満に戻さなければならない.という問題.

xが2200以上になったら次で2200未満に戻さなければならないという制約をわすれてexample3おかしくない?とか言ってた(アホ).DPでもしないと求まらなそうだな,という気持ちになるのでその方向性でかんがえると"dp[i][j]=i回目の操作のあとx=jになっているときのまたいだ回数の最大値"というDPが浮かぶ.このままだとxに上限がなくて出来ないが,この制約のおかげである操作で一瞬xが2200以上になっても次の操作で2200未満になるので,そういう場合は2つの操作をまとめてやることで常にxが2200未満となって出来る.