TopCoder Open 2012 Round 2A Div1 Medium CucumberWatering

問題

n個のきゅうりに水をやりたい。
きゅうりは一次元の直線上に並んでいて、それぞれの座標はx[i]である。
きゅうりには、与えられた順番で水をやる必要がある。

座標平面上にはk個、テレポーターを自由な場所に設置することができて、
テレポーターを使うことで、テレポーター間を距離0で移動できる。
テレポーターを最適に配置したとき、全てのきゅうりに水をやるのに必要な移動距離の最小値を求めよ。

制約条件

-10^9≦x[i]≦10^9
n, k≦50

方針

動的計画法による。
テレポーターはきゅうりと同じ点に置く場合しか考えなくてよい。

区間ごとに移動をわけて考える。
rec(pos, k)を、posの位置にテレポーターを置き、
あとk回テレポーターを置けるようなときのpos以降の区間における移動距離の最小値とする。

これは、次にテレポーターを置く位置をpos+1からn-1まで試して、再帰することで求まる。
この関数recをメモ化すれば計算量は全体でO(n^2)になる。

ソースコード

以下のコードでは、pos+1からiまでの移動距離を毎回計算しているため計算量はO(n^3)になっている。

int n;
vi x;
ll dp[51][51];

ll rec(int pos, int k){
	if(k < 0) return 1ll << 60;
	ll &res = dp[pos][k];
	if(res >= 0) return res;
	res = 0;
	rep(i, n - 1){
		int x1 = max(x[pos], x[i]);
		int x2 = max(x[pos], x[i+1]);
		res += abs(x2 - x1);
	}
	rep(i, n) if(x[i] > x[pos]){
		ll tmp = rec(i, k - 1);
		rep(j, n-1){
			int x1 = max(x[pos], min(x[i], x[j]));
			int x2 = max(x[pos], min(x[i], x[j+1]));
			tmp += min(abs(x2 - x1), x[i] - abs(x1 - x2) - x[pos]);
		}
		res = min(res, tmp);
	}
	return res;
}

class CucumberWatering {
	public:
	long long theMin(vector <int> x, int K) 
	{
		n = x.size();
		::x = x;
		memset(dp, -1, sizeof(dp));
		ll ans = 0;
		rep(i, n-1) ans += abs(x[i] - x[i+1]);
		
		rep(i, n){
			ll tmp = rec(i, K - 1);
			rep(j, n-1){
				int x1 = min(x[j], x[i]);
				int x2 = min(x[j + 1], x[i]);
				tmp += abs(x1 - x2);
			}
			ans = min(ans, tmp);
		}
		return ans;
	}
};