Noelちゃんと星々3 [yukicoder No.838] - はまやんはまやんはまやん

前提知識

DPテク17「遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる」

解説

まず、前の問題が解けないと解けないので、こちらを理解する。
get(L, R) := [L,R)を1点に集めるときのコスト最小値
区間でまとめていく問題なので、DPでうまくやれそう。
問題が遷移の多さであるが、状態数O(N)で遷移先もO(N)ありそう。
しかし、遷移先は貪欲にやることでもう少し減らせる。
例えば6個を1箇所にまとめることを考えると、前半3つと後半3つで2箇所にまとめた方がコストがよくなりそうである。
なので、問題がその何個でまとめるのが最大最適かであるが、計算量と相談して、最大の数を選んでもいいが、なんとなく5個でやったら通った。
3個くらいが最大っぽい感じがする。

int N; ll Y[101010];
BIT<ll> bit(101010);
ll dp[101010];
//---------------------------------------------------------------------------------------------------
ll get(int L, int R) { // [L, R)
	int C = (L + R) / 2;

	ll res = 0;
	res += 1LL * (C - L) * Y[C] - bit.get(L, C);
	res += bit.get(C, R) - 1LL * (R - C) * Y[C];
	return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> Y[i];
	sort(Y, Y + N);
	rep(i, 0, N) bit.add(i, Y[i]);

	rep(i, 0, N + 1) dp[i] = infl;
	dp[0] = 0;

	rep(i, 0, N) {
		rep(j, i + 2, N + 1) {
			if (5 < j - i) break;
			chmin(dp[j], dp[i] + get(i, j));
		}
	}

	cout << dp[N] << endl;
}