ABC163 E - Active Infants (500)
最初の考察
$ A_iが大きいのを左右の端に置く方が必ず良い
そうで無い場合、端になるように交換すると総移動距離は変わらないが$ A_iが大きい方の移動距離が増えてうれしさが増える
$ A_iが大きい順に貪欲に左右どちらに持って行けば良いか決める
大きい順はpairなどで持っておく
入力2が通らない
$ [1,1,1,5,5,6] より$ [6,1,1,1,5,5] の方が良くなる
最終的な考察
大きい方から決めるのは同じ
置ける中での左右の端のどちらかにおいてメモ化再帰する
$ dp[i][(l,r)] でi番目まで置き方を決めて、残っている区間が$ (l,r)の時の最大のうれしさ
左右どちらかの端に置くので残りの区間は必ず連続
$ (l,r)はl,rどちらかだけ持っていても問題ない
各置き方は高々1回しか呼ばれないのでN個のに対して$ O(N)の区間が考えられるので$ O(N^2)