yukicoder No.31 悪のミックスジュース
解法
まず, N >= V の場合はそれぞれのジュースを 1 リットルずつ買って適当に分配すれば良いです。
V > N の場合もとりあえずすべてのジュースを 1 リットルずつ買っておけば「使わない果物があってはいけない」という制約を考える必要がなくなるので, 買ったことにして, V から N を引いておきます。
問題を線形計画問題っぽく定式化すると,
min
s.t.
となります。
ですが, このままだとよくわからないので更に変形していきます。 とおくと,
となります。同様に,
という制約式も,
という制約式になります。
また, の定義から, が制約になります。よって, 問題は
min
s.t.
となります。
これならなんかいけそうです。というか, この問題は yukicoder No.288 と同じように解くことが出来ます。mayokoex.hatenablog.com
No.288 と同じように, V が大きいことがネックですが, 鳩の巣原理を使うと, の値がなるべく大きい物を選ぶだけで のところまでは決めることが出来ます。あとは動的計画法でがんばりましょう。
const int MAXN = 111; const ll INF = 1ll<<60; ll C[MAXN], S[MAXN]; pair<ll, int> P[MAXN]; ll dp[MAXN][MAXN*MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; ll V; cin >> N >> V; for (int i = 0; i < N; i++) { cin >> C[i]; } S[0] = C[0]; P[0] = make_pair(S[0], 1); for (int i = 1; i < N; i++) { S[i] = S[i-1] + C[i]; P[i] = make_pair(S[i], i+1); } ll ans = S[N-1]; V -= N; if (V <= 0) { cout << ans << endl; return 0; } sort(P, P+N, [](const pair<ll, int>& lhs, const pair<ll, int>& rhs) -> bool {return lhs.first*rhs.second < rhs.first*lhs.second;}); // V の残りが N^2 になるまでは引いていっても良い ll ok = V-N*N; if (ok > 0) { ll num = ok/P[0].second; if (ok%P[0].second) num++; ans += P[0].first*num; V -= P[0].second*num; } assert(V <= N*N); // 後は dp for (int i = 0; i < N; i++) for (int j = 0; j <= N*N; j++) dp[i][j] = INF; dp[0][0] = 0; for (int i = 0; i < N; i++) { if (i > 0) { for (int j = 0; j <= N*N; j++) { dp[i][j] = min(dp[i][j], dp[i-1][j]); } } for (int j = 0; j <= N*N; j++) { if (j-(i+1) >= 0) dp[i][j] = min(dp[i][j], dp[i][j-i-1]+S[i]); } } cout << ans + dp[N-1][V] << endl; return 0; }