ABC163 E - Active Infants - かんプリンの学習記録

問題概要
思考の流れ
証明
提出プログラム
感想

問題概要

${2\le N\le 2000}$ 人の幼児が左右一列に並んでおり, 左から ${i}$ 番目の幼児の活発度は ${1\le A_i\le 10^9}$ である. 幼児の順番を好きに並び替える. はじめ左から ${x}$ 番目に並んでいた幼児が左から ${y}$ 番目に移動するとき,うれしさが ${A_x×|x−y|}$ だけ生じる. 幼児のうれしさの合計の最大値を求めよ.

思考の流れ

まず, 活発度の高い幼児から順に一番遠いところに入れるgreedyを思い付くが, 入力例2などで不正解となる.
なぜダメかというと ${6}$ を右に入れたせいで ${2}$ つの ${5}$ が一つ左にずれてうれしさが減少したから.
この場合, ${6}$ を左端に入れるべきだった.

${\downarrow}$

大きい順に入れていくのはいいとして, 左右どちらに入れるのがよいか. 全探索しようとすると ${2^N}$ 通り試す必要がある.
左右から数字が埋まっていく. ある数字を左右どちらに入れるか考えるときに, 今まで入れた数字がそれぞれどこにあるかは関係なく, 左右の数字がどこまで埋まっているかがわかればよさそう.

${\downarrow}$

DPをする. ${dp[i][j]}$ を「左から ${i}$ 番目, 右から ${j}$ 番目までが埋まっているときの最大値」とすると更新式は, ${B_i}$ を「活発度が大きい方から ${i}$ 番目の幼児の活発度」, ${t_i}$ を「活発度が大きい方から ${i}$ 番目の幼児の元の位置」として