SRM 217 DIV1 Hard TeleportAndLoader

問題 Editorial

問題

今位置0に荷物がNつある。
この荷物たちをそれぞれ指定された位置boxesに移動したい。
移動するのに2つの方法がある。
一つ目がテレポート。これは複数の荷物をまとめて、任意の位置へ移動できる。ただし1回に1つの位置にしか移動できない。
1回使うたびに、荷物がどんな数あってもどんな位置でも同じコストteleport_costで移動できる。
2つ目がローダー。これは荷物を一つずつ・左右に距離1ずつ移動できる。一回使うたびにloader_costがかかる。
このとき、最小コストを求めよ

• 1 <= N <= 50

解答

まず、「何個かまとめてテレポート→ローダーで調整」もしくは「テレポーター使わずにローダーだけで移動させる」という操作のみで最小コストにできる。
またテレポートをまとめて行う時、近い位置の荷物たちを移動させるのがよく、つまり位置でソートしたときに区間で表せるまとめかただけを考えれば良い。
テレポートさせる時にどの位置に移動させればよいかだが、これは荷物の位置たちの中央値を取れば良い。
あとはそれをDPでやる

コメント

Σ{|a[i]-x|}の最小化は中央値がいいというのは、恐らく簡単に証明・理解できるのだろうが、自分は"東京大学プログラミングコンテスト2012 L じょうしょうツリー"の解説http://www.utpc.jp/2012/で初めて知った。常識なのかね？
この程度のDPは簡単に素早く解けなければいけないね

コード

#include <vector>
#include <algorithm>
#include <cstring>
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define all(o) (o).begin(), (o).end()
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi; typedef long long ll;
ll dp[55];
struct TeleportAndLoader {
	vi x; int n; ll tc, lc;
	ll rec(int i) {
		if(dp[i] != -1) return dp[i];
		ll r = INF;
		if(i == n) r = 0;
		else {
			r = min(r, lc * x[i] + rec(i+1));
			rer(t, 1, n-i) {
				int c = 0; int y = x[i+t/2];
				reu(j, i, i+t) c += abs(y - x[j]);
				r = min(r, tc + lc * c + rec(i + t));
			}
		}
		return dp[i] = r;
	}
	int cheapTransportation(vector <int> boxes, int teleport_cost, int loader_cost) {
		x = boxes; n = x.size(); sort(all(x)); tc = teleport_cost, lc = loader_cost;
		mset(dp, -1);
		return rec(0);
	}
};