きままにものづくり

日々の気付いたことなんかを書いてます。

SRM602Div1Easy

問題

サイズNの数列と初期値Xが与えられる。与えられた順番のままで、現在の値に要素を足したり、引いたりすることができる。はじめの値はXとなる。2200以上の値を連続させることはできない。2200以上になる回数と2200より小さくなる回数の合計の最大値を求めよ。

解法

dp[i番目の要素][値]として動的計画法を使用して求めることができる。

計算量

 O(BN)
B:2200
N:数列の要素数

コード