UVa 10163 - Storage Keepers

链接

传送门

题意

有$n$个仓库,$m$个管理员,每个管理员有一个能力值$p[i]$,雇佣管理员的花费与能力值相同。一个仓库的安全度为$p[i]/k$,其中$k$为管理员管理仓库的个数,求最小安全度的最大值和此时的花费。

思路

定义状态$dp[i][j]$为前$i$个管理员管理前$j$个仓库时的最小安全度的最大值。有$dp[i][j]=\max\{\min\left(dp[i-1][j-k],p[i]/k\right)\}$。求花费的方法与之类似。

代码

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
48
49
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
int p[maxn];
int dp[maxn][maxn];
int main() {
int n, m;
while (~scanf("%d%d", &n, &m) && (n || m)) {
for (int i = 1; i <= m; ++i) {
scanf("%d", &p[i]);
}
memset(dp, 0, sizeof dp);
for (int i = 1; i <= m; ++i) {
dp[i - 1][0] = inf;
for (int j = 1; j <= n; ++j) {
dp[i][j] = dp[i - 1][j];
for (int k = 1; k <= j; ++k) {
dp[i][j] = max(dp[i][j], min(dp[i - 1][j - k], p[i] / k));
}
}
}
int ans = dp[m][n];
if (ans == 0) {
puts("0 0");
continue;
}
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= m; ++i) {
dp[i - 1][0] = 0;
for (int j = 1; j <= n; ++j) {
dp[i][j] = dp[i - 1][j];
for (int k = 1; k <= j; ++k) {
if (p[i] / k >= ans) {
dp[i][j] = min(dp[i][j], dp[i - 1][j - k] + p[i]);
}
}
}
}
printf("%d %d\n", ans, dp[m][n]);
}
return 0;
}