問題概要
果物$[1,N]$ある。今ミックスジュースを$V$リットルだけ作らなくてはいけない。それぞれの果物は1リットル作るのに$C[i]$円必要である。 すべての果物を購入して$V$リットル以上作りたい。 ミックスジュースの果物$k$が占める割合pkは、$p1≥p2≥⋯≥pN$でなくてはならないという条件のもと、$V$リットルのジュースを作るコストを最小化せよ。
$N\leqq10^2$、$V\leqq10^9$、$C[k]\leqq10^9$
解法
$p1≧p2…$みたいな制約は、$p3$を選択したいときは$[p1,p3]$をすべて購入しなければならないということになる。
したがってこの問題は以下のように言い換えられる。
$cost[i]:= [1,i]$を使用するのにかかるコストとして、
長さ$i(0<i≦N≦10^2)$の線分がある。これを使用するコストは$cost[i]$である。
長さ$V$以上$(≦10^9)$の線分を作るのに必要な最低コストは?
ただし必ず$cost[N]$は一度使用する。
一見$DP$でできそうだけど、$O(NV)$かかってしまう。
そこで線分の長さに着目すると、$V$が大きいときにある程度は$cost[i]$が小さい線分を選択し、最後$N^2$以下の線分については最適値を当てはめればよい。
ある程度貪欲パートがつくことで、$O(N*N*MAX_L)$まで計算量を落とすことができ、これは簡単な組合せで解ける。
計算量:$O(N^2*MAX\_L)$
ソース
#include <bits/stdc++.h> using namespace std; using VS = vector<string>; using LL = long long; using VL = vector<LL>; using VVL = vector<VL>; #define SZ(a) int((a).size()) #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++) const int INF = 1e9; const LL LINF = 1e18; LL solve(LL left, VL& a) { // left リットルつくるときにかかる最小コスト、ただしany i, a[i]>=a[i+1] int N = SZ(a); VL sum(N + 1, 0); FOR(i, 0, N) { sum[i + 1] = sum[i] + a[i]; } VL dp(10001, LINF); dp[0] = 0; FOR(i, 1, N + 1) { FOR(j, 0, 10001) { if (i + j <= 10000) dp[i + j] = min(dp[i + j], dp[j] + sum[i]); } } LL ret = LINF; FOR(i, 1, N + 1) { FOR(l, 0, 10001) { if (left - l >= 0 && (left - l) % i == 0) { int backet = (left - l) / i; ret = min(ret, dp[l] + sum[i] * backet); } } } return ret; } LL N, V; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> N >> V; VL a(N); LL sum = 0; // これだけは必ず必要 FOR(i, 0, N) { cin >> a[i]; sum += a[i]; } if (N >= V) { cout << sum << endl; } else { cout << sum + solve(V - N, a) << endl; } return 0; }