問題
提出コード
問題の制限をきちんと見れば、全探索で間に合うということがわかります。
が、特に何も考えていなかったので累積和をとりました。
この問題では、下に1回、右に回移動する操作を行うだけなので、
回右に移動して下に移動、そして最後に残りの分だけ右に移動する、という操作しかできません。ということで、この
について全探索を行います。
ということで、上の段と下の段それぞれについて、左端から番目まで移動したときに獲得できるキャンディーの量を累積和で記録します。 そうすることで、
番目で下の段に移動した場合に獲得できるキャンディーの量は
(1~の区間の上の段のキャンディーの総和)+(
~
の区間の下の段のキャンディーの総和)
と表すことができ、これの最大値を求めれば答えとなります。
