yukicoder 31 - 悪のミックスジュース

類題
creep06.hatenablog.com

問題

果物1、果物2、...、果物nの、それぞれの100%ジュースを混ぜて、ミックスジュースをvリットル作りたい
果物iの100%ジュースは1リットルパックがc[i]円で売られている
ミックスジュースを作るための最小コストを求めよ

ただしミックスジュースにおいて果物iが占める割合はp[1]>=p[2]>=...>=p[n]である必要がある
また使わない果物があってもいけない
1リットルパックを買ってその一部のみを使っても良い

1 <= n <= 100
1 <= v <= 10^9
1 <= c[i] <= 10^9

解法

使わない果物があってはいけない制約より、まず各ジュースを1リットルずつ買ってしまっていい
(その時点でvリットル以上になる場合はΣc[i]を出力して終了)

(以下iは1-based)
次に果物の割合の制約は、「i番目の果物を1リットル増やすとき、i-1番目までの果物も全て1リットルずつ増やさないといけない」と言い換えられる
こう言い換えるとi番目のジュースは「iリットルでΣc[1,i] (この値をs[i]とする)円であるようなジュースパック」と見なせる
すると各パックは1リットルあたりs[i]/iだから、一番安いパックでVの大半を埋めてしまえばいい

ちなみにコード中では1リットルあたりの値段の大小は
s[x]/x <=> s[y]/y
→ s[x] * y <=> s[y] * x
と変形して計算した

「大半」というのはどれくらいかと言うと、↑で求めた一番得なパックをm、そうでないパックをtとすると、tをmパック買うよりmをtパック買ったほうが得だから、m以外の各パックは全て合わせてもたかだかn^2リットルしか買わなくていい
すると
dp[i][j]: i番目のパックまででjリットル買うときの最小コスト
という、テーブルのサイズがn^3で更新にO(n)かかる計O(n^4)のdpができる
これを計算した後、(v-i)がmで割り切れるような各iで「dp[n][i] + (パックmをv-iリットル分買うコスト)」で答えを更新していけばいい

#define int long long

int n, v, c[101], s[101], mn, dp[101][10010], res = linf;

signed main() {
	cin >> n >> v;
	rep(i,n) {
		cin >> c[i];
		s[i] = c[i] + (i ? s[i-1] : 0);
	}
	v -= n;
	if (v<=0) return cout << s[n-1] << endl, 0;
	rep(i,n) if (s[i]*(mn+1)<s[mn]*(i+1)) mn = i;

	rep(i,101) rep(j,10010) dp[i][j] = 1ll<<60;
	dp[0][0] = 0;
	rep(i,n) rep(j,10010) rep(k,101)
		if (j+k*(i+1)<=10000) chmin(dp[i+1][j+k*(i+1)], dp[i][j] + s[i]*k);
	rep(i,min(10001ll,v)) if ((v-i)%(mn+1)==0) chmin(res, (v-i)/(mn+1)*s[mn] + dp[n][i]);
	cout << res + s[n-1] << endl;
}