有 $n$ 个仓库，让 $m$ 个人来看管。一个仓库只能由一个人来看管，一个人可以看管多个仓库。
每个人有一个能力值 $p_i$，如果他看管 $k$ 个仓库，那么所看管的每个仓库的安全值为 $\lfloor \frac {p_i} {k}\rfloor$
如果某个仓库没有人看管，那么它的安全值为 $0$。所有仓库的安全值 $L$ 为所有仓库安全值的最小值
如果雇佣一个人的工资等于他的能力值 $p_i$。
从 $m$ 个人中选择一些人雇佣，问所有仓库的安全值最高是多少，在安全值最高的情况下，求雇佣的最少价钱。
链接
UVA 10163
题解
考虑分成两段来 DP
$f[i][j]$ 表示前 $i$ 个人，管理 $j$ 个仓库的最大安全值，则
$$f[i][j] = \max\big\{\min\{f[i - 1][j - k] + \frac {p[i]} {k}\}\big\}, \ \ 0 \leq k \leq j \leq n$$
$g[i][j]$ 表示前 $i$ 个人，管理 $j$ 个仓库的安全值达到最大值的情况下所用的最少价钱
$$g[i][j] = \min\{g[i - 1][j - k] + p[i]\}, \ \ \frac {p[i]} {k} \geq f[m][n]$$
时间复杂度 $O(n ^ 2m)$
代码
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
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <bits/stdc++.h>
namespace {
const int MAXN = 110;
int n, m, f[MAXN][MAXN], g[MAXN][MAXN], p[MAXN];
inline void solve() {
while (std::cin >> n >> m && n && m) {
for (register int i = 1; i <= m; i++) std::cin >> p[i];
memset(f, 0, sizeof(f));
for (register int i = 1; i <= m; i++) {
f[i - 1][0] = 0x3f3f3f3f;
for (register int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][j];
for (register int k = 1; k <= j; k++)
f[i][j] =
std::max(f[i][j], std::min(f[i - 1][j - k], p[i] / k));
}
}
memset(g, 0x3f, sizeof(g));
for (register int i = 1; i <= m; i++) {
g[i - 1][0] = 0;
for (register int j = 1; j <= n; j++) {
g[i][j] = g[i - 1][j];
for (register int k = 1; k <= j; k++)
if (p[i] / k >= f[m][n])
g[i][j] = std::min(g[i][j], g[i - 1][j - k] + p[i]);
}
}
std::cout << f[m][n] << ' ' << (f[m][n] == 0 ? 0 : g[m][n]) << '\n';
}
}
}
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
solve();
return 0;
}
|
