「UVA 10163」Storage Keepers-DP

有 $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
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「UVA 10163」Storage Keepers 22-10-2017
* DP
* @author xehoth
*/
#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;
}
# DP

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×