CF Beta Round 38 E. Lets Go Rolling!

問題

直線上にビー玉がいくつかあって，ビー玉は各ビー玉に割り当てられたコストを払うことで固定することができる．
ビー玉を質点とし，左へ転がる場合，(固定したビー玉のコストの和)+(動いたビー玉の距離の和)を最小化する．
ただし，各ビー玉の位置と固定するコストは-10^9から10^9まで．

考え方

dp．
まず，一番左にあるビー玉は絶対固定しないと移動距離が無限大になってしまう．
dp[固定した一番右端のビー玉][注目するビー玉]=コストの総和と考えると，dp[0][0]は一番左のビー玉を固定するコストで，
dp[j][i] = min(dp[j][i-1]+移動距離, dp[j-1以下][i-1]で最小のもの+固定コスト)になる．
「dp[j-1以下][i-1]で最小なもの」は毎回計算せず，各jが終わった後で別な配列に最小値を保持しておく．
最終的に，i=n-1で一番小さいものが答え．