ABC163 E. Active Infants

問題

N人の幼児が一列に並んでいる。左からi番目の幼児の活発度はA_iである。

幼児たちを1回だけ任意の順番に並び替えることができ、並び替える前にx番目にいた幼児が並び替え後にy番目になった場合、その幼児のうれしさはA_i * |x-y|になる。

うれしさの合計は最大でいくつにできるか、求めよ。

制約

• 2 <= N <= 2000
• 1 <= A_i <= 10^9

解法

i番目にいる幼児のうれしさは「A_i * | i - 移動先 |」となっている。
A_iが大きい幼児から考えると、できるだけ前方か後方に移動したほうが絶対値の中が大きくなるので、そのように動かしたい。

各幼児について、できるだけ前方に配置するか、できるだけ後方に配置するか、が考えられるので、これをdpで求める。
dp[x][y] := 前方にx人、後方にy人すでに配置しているときのうれしさの最大値
とすると、(x,y)のときに前方に配置するか後方に配置するかの遷移で更新できる。
最終的にdpで最大値を答えれば良い。