ABC163 E - Active Infants (500)

問題：E - Active Infants

解答：Submission #12999465 - AtCoder Beginner Contest 163

解法：dp[x][y] : 左にx人移動させ、右にy人移動させたときの活発度の合計の最大値、としてdpする。移動させるのは活発度が大きい順で、左・右から詰めるように移動させると活発度が最大になる。

イメージとしては、活発度が大きい人から順番により遠くに移動させるのがよいが、右か左かどちらに移動したらいいかは最後まで分からないのでDPになる、ということなのだろう。

それと、添字も大きい順に動かすことにしたが、これも全員同じ活発度の時に効いてきそう（真ん中の人から先に動かすとよくなさそう）。