CODE FESTIVAL 2016 Grand Final,F: Intervals

https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_f

まず真ん中の区間を動かさないで最小を達成する方法があることが示せます。
なので右左にそれぞれN/2個の区間を割り振ればいいです。
そして貪欲が厳しそうだと思えるのでDPをしようとするんですが、ここが思いつきませんでした。

大きい区間から真ん中に置いていきます。次の区間は真ん中から他の区間を押し出すように挿入します。
あとはdp[i][j][k]:=(右i個左j個真ん中k個(0or1)おいた時の最小コスト)で解けます。

要はDPに落としこむために順番を変えて見ればよかったわけですね。

あとsort関数で>=を使ってバグらせたんですが、今まで経験なかったのが不思議。明確に>にしましょう。

int N;
pl I[5010];
ll dp[2510][2510][2];

bool compare(const pl& p1, const pl& p2) {
	return (p1.sec + p1.fst) > (p2.sec + p2.fst);
}

void solve() {
	cin >> N;
	rep(i, 0, N) {
		ll l, r;
		cin >> l >> r;
		I[i] = pl(l, r);
	}
	sort(I, I + N, compare);

	int LN = (N - 1) / 2, RN = N / 2;

	rep(i, 0, LN + 1) {
		rep(j, 0, RN + 1) {
			dp[i][j][0] = linf;
			dp[i][j][1] = linf;
		}
	}

	dp[0][0][0] = 0;

	rep(i, 0, LN + 1) {
		rep(j, 0, RN + 1) {
			rep(k, 0, 2) {
				if(dp[i][j][k] == linf) continue;
				int id = i + j + k;
				ll l = I[id].fst, r = I[id].sec;
				if(i < LN) MIN(dp[i + 1][j][k], dp[i][j][k] + (l + r) * (i + 1) - l);
				if(j < RN) MIN(dp[i][j + 1][k], dp[i][j][k] + (l + r) * (j + 1) - r);
				if(k == 0) MIN(dp[i][j][k + 1], dp[i][j][k] + l * LN + r * RN);
			}
		}
	}
	cout << dp[LN][RN][1] << "\n";
}