链接
传送门
题意
有\(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;
}
|