SRM646のDiv1 Easyと似てるなぁ。
http://community.topcoder.com/stat?c=problem_statement&pm=13602
問題
1本の長い線路の上にN個の車両がある。
各車両は位置P[i]から長さL[i]を占めている。
各車両を線路に沿って移動させ、全体を1つに連結したい。
各車両の移動距離の総和の最小値を答えよ。
解法
まず全体を位置順にソートしておく。
この問題は、N台の車両のうち真ん中の車両に向かって両側から寄せていくだけで良い。
以下のように考えると理解できる。
左にP台が1個に連結した車両群、右にQ台が1個に連結した車両群があって、これらを連結したいとする。
左のP台を1右に動かすと、移動距離の総和はP増え、右のQ台を1左に動かすと、移動距離の総和はQ増える。
そう考えると少ない方の車両群を動かした方が移動距離の総和が短くなる。
以下のコードでは、念のため各車両を固定してそこに他の車両を寄せるパターンを全部試している。
class ConnectingCars { public: pair<ll,ll> P[101]; ll dist[101][101]; int N; long long minimizeCost(vector <int> positions, vector <int> lengths) { int i,j,x,y; N=positions.size(); FOR(i,N) P[i]=make_pair(positions[i],lengths[i]); sort(P,P+N); FOR(y,N) FOR(x,y) { ll tot=P[y].first-P[x].first; for(i=x;i<y;i++) tot-=P[i].second; dist[x][y]=dist[y][x]=tot; } ll mi=1LL<<60; FOR(i,N) { ll tot=0; FOR(j,N) tot+=dist[i][j]; mi=min(mi,tot); } return mi; } }
まとめ
Div2 Mediumにしては簡単だけど、Div2 Easyにしては難しいかも。