Static Sushi
問題はこちら atcoder.jp
自分が気づいたところ
最大でも反対方向に向きを変える動きは一回だけなので，反転する場所を一つ決めてそこから反転した後の最大値を求めることを考えた．
これだと，計算量は反転する場所が ，反転後の最大値探索が累積和を使うと
で
になるので，部分点はもらえる．
Submission #4898403 - AtCoder Beginner Contest 095
しかし，ここから計算量をどうやって落とすのかが理解できなかった．
解説を読んで
「最大値を保持」しておけば良い．ということがわからなかったので，以下のブログを参考にした．
http://blog.livedoor.jp/misteer/archives/9017497.htmlblog.livedoor.jp
最大値をdpの値として持っておいて，逐次更新していく．
自分の詰まったところ
取得カロリーの累積和を事前に計算しておき，dpの更新時に距離分の消費カロリーを引く．自分は逐次差分 を追加していく方法だったが，これだと例えば一個飛ばして更新が発生した時に正しく消費カロリーが計算されない．
Submission #4900921 - AtCoder Beginner Contest 095
学んだこと
- 最大値dpという考え方．「iまでの最大値」という値の持ち方をすることで計算量が下がる時がある．
- 往復可能なものについては，折り返しが何回起きうるかを考えてみる（だいたい1回で十分な時が多い）．
