停止コストを最小化する
アプリ $i$ を停止するとメモリ $m_i$ を解放でき、コスト $c_i$ がかかる。解放したメモリの合計を $M$ 以上にしながら、コストの合計を最小化する。
必要メモリを状態にすると配列が大きくなりすぎる。一方、アプリ数は最大100、各停止コストは最大100なので、コストの合計は最大10,000である。そこでコストをDPの状態にする。
DPの不変条件
best[b] を、コストを最大 $b$ まで使って解放できる最大メモリ量と定義する。コストがちょうど $b$ の状態ではなく、$b$ 以下の予算を表す。そのため、すべての要素を0で初期化できる。
各アプリについて、停止しない場合と停止する場合を比較する。
\[\text{best}[b] = \max(\text{best}[b],\ \text{best}[b-c_i] + m_i).\]同じアプリを二度選ばないよう、予算を大きい方から更新する。コストが0のアプリも、そのアプリについて各予算を一度だけ更新するため正しく扱える。best[b] >= M を満たす最小の $b$ が答えとなる。
正しさ
最初の $i$ 個のアプリだけを考えたとき、best[b] はコストを最大 $b$ まで使って得られる最大メモリ量だと仮定する。次のアプリを停止しない場合は従来の状態を保ち、停止する場合はコスト $c_{i+1}$ 分を引いた予算の状態にメモリ $m_{i+1}$ を加える。漸化式はこの二つのケースの大きい方を選ぶため、不変条件が保たれる。予算を降順に更新することで、現在のアプリを反映する前の状態だけを参照し、同じアプリの再利用を防ぐ。よってすべてのアプリを処理した後、初めて $M$ 以上を得る予算が最小コストである。
時間計算量は $O(NC)$、空間計算量は $O(C)$ である。ここで $C=\sum_i c_i$ とする。
C++17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, required_memory;
cin >> n >> required_memory;
vector<int> memory(n), cost(n);
for (int& value : memory) cin >> value;
for (int& value : cost) cin >> value;
const int total_cost = accumulate(cost.begin(), cost.end(), 0);
vector<int> best(total_cost + 1, 0);
for (int i = 0; i < n; ++i) {
for (int budget = total_cost; budget >= cost[i]; --budget) {
best[budget] = max(best[budget], best[budget - cost[i]] + memory[i]);
}
}
for (int budget = 0; budget <= total_cost; ++budget) {
if (best[budget] >= required_memory) {
cout << budget << '\n';
return 0;
}
}
cout << -1 << '\n';
}
出典と改訂履歴
MINJUN PARKが2022-04-18に公開し、CC BY 4.0を表示した「백준 7579번 - 앱」を基にした。コストを状態にする0/1ナップサックの方針は維持し、DP状態が「費用ちょうど」ではなく「予算以下」であることを明確にした。GNUの可変長配列は標準C++17のコードに置き換えた。