Codeforces 321(#190 Div1) E. Ciel and Gondolas

問題

n人の人が一列に並んでいて、k個のゴンドラにわけて乗せる。
一つのゴンドラには何人でも乗れるが、乗せる順番は並び順でなければならない。

人同士には仲の悪さが決まっていて、i番目とj番目の人の仲の悪さはa[i][j] (=a[j][i]).
一つのゴンドラ内の不幸せさは、ゴンドラ内の全ての二人i, jについてΣa[i][j].
乗せ方を最適にしたとき、全てのゴンドラの不幸せさの総和の最小値を求めよ。

制約条件

n≦4000, k≦800
0≦a[i][j]≦9
a[i][j] = a[j][i], a[i][i] = 0

方針

Monge系のDP.
dp[i][j] := i個のグループに分けて先頭j人を乗せるときの最適解
としたとき、これを更新するDPは、時間計算量がO(kn^2).

この問題だとA[i][j] = argmin_k{dp[i][j] = dp[i-1][k] + cost[k][j]}としたとき、
A[i][j]≦A[i][j + 1]が成り立つらしい。証明まだ理解してないので後で理解したら書く。
参考→http://www.ics.uci.edu/~eppstein/pubs/EppGalGia-FOCS-88.pdf

とりあえずコストの関数cost(i, j)がMongeなのは、
Monge⇔cost(i, l) + cost(j, k) ≧ cost(i, k) + cost(j, l)が成り立っていること。
この場合cost(i, l) + cost(j, k) = cost(i, k) + cost(j, l) + 2 * cost(k, l)
が成り立っていて、cost(x, y)≧0だから。

なので分割統治法で、
rec(l, r, kl, kr)でdp[g][l]からdp[g][r]を計算する関数として、
m = (l + r) / 2に対してdp[g][m]を最適にするkを求めて、
rec(l, m, kl, k + 1)
rec(m, r, k + 1, r)を再帰的に呼べば計算量がO(knlogn)に減る。

入力が1600万もあるのでscanfすると死ぬ。
文字列として一行ずつ読んで自力でパーズしないとダメ。

ソースコード

const int MX = 4010;
int n, g, a[MX][MX], cost[MX][MX];
int dp[MX][MX];
char buf[2 * MX];

inline void rec(int g, int l, int r, int kl, int kr){
	if(kl + 1 == kr){
		for(int i = l; i < r; i++) dp[g][i] = dp[g - 1][kl] + cost[kl][i];
		return;
	}
	int m = (l + r) / 2, k;
	dp[g][m] = inf;
	for(int i = kl; i < kr && i < m; i++) if(dp[g][m] > dp[g - 1][i] + cost[i][m]){
		k = i;
		dp[g][m] = dp[g - 1][i] + cost[i][m];
	}
	if(l + 1 == r) return;
	
	rec(g, l, m, kl, k + 1);
	rec(g, m, r, k, kr);
}

int main(){
	scanf("%d%d", &n, &g);
	gets(buf);
	rep(i, n){
		gets(buf);
		rep(j, n) a[i][j + 1] += a[i][j] + buf[2 * j] - '0';
	}
	rep(i, n) for(int j = i + 1; j <= n; j++) cost[i][j] = cost[i][j - 1] + a[j - 1][j] - a[j - 1][i];
	
	rep(i, n + 1) dp[1][i] = cost[0][i];
	rep(i, g - 1) rec(i + 2, 0, n + 1, 0, n);
	cout << dp[g][n] << endl;
	
	return 0;
}