はまやんはまやんはまやん

hamayanhamayan's blog

Noelちゃんと星々3 [yukicoder No.838]

https://yukicoder.me/problems/no/838

解説

https://yukicoder.me/submissions/352656

まず、前の問題が解けないと解けないので、こちらを理解する。
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;
}