前言

题目链接

我们教练十分努力,竟然找到了这个只有一百多人做的题目。

这是一道比较有思维难度的 01 背包题,建议评绿或者蓝?


确定容量和价值

这个输入的变量名很显然就是在提示你把计算机和客户订单混在一起嘛。

我们可以发现,对于每一个计算机,只有买或不买两种情况;对于每一个单子,只有接或不接两种状态。 而能不能接客户的单子取决于内核的数量够不够。于是,我们想到了这道题的算法——01 背包,内核数量相当于容量,钱相当于价值。

但是这时就有了一个问题:我怎么确定内核的数量?

注意到题目中还有另一个条件——时钟频率。因为客户要求有一个对于时钟频率的限制,换句话说,就是每一个客户能使用的最大内核数量是确定的

所以我们可以把计算机和客户的单子放在一个结构体数组里面,拿一个 bool 区分一下计算机和客户。然后,按照时钟频率排序。

此时,对于任意一个客户的单子,它前面的所有内核数量之和就是对于它来说可以使用的最大内核数。

这里需要注意一点:如果时钟频率一样,计算机排在前面。如果类型和时钟频率都一样,计算机把价格低的排在前面,客户把价格高的排在前面。

1
2
3
4
5
6
7
8
9
bool cmp(node x, node y) {
if(x.f != y.f)
return x.f > y.f;
if(x.data != y.data)
return x.data < y.data;
if(!x.data)
return x.v < y.v;
return x.v > y.v;
}

状态转移

接着就到了比较难的地方。

设 $dp_{i,j}$ 代表处理了前 $i$ 个请求之后还剩下 $j$ 个可用的内核时能获得的最大利润。

经上文分析,对于计算机和客户都有两种状态。那么,选择哪种更优呢?

我们用一个变量 $C$ 来统计到目前为止内核的总数量,相当于一个前缀和。然后分析:

对于计算机

买的话,需要花钱,但是内核数量会增加。那么相对买之前来说,买后内核数量增加了 $c_i$,也就是说买之前内核数量比现在少 $c_i$,而买后,现在有的钱数量相较于买之前减少了 $v_i$,所以结果表达式如下:

至于 $j$ 的循环范围很简单,保证数组下标不超过 $0\sim n$ 的范围即可。

所以就有对于计算机的状态转移方程:

对了,记得在转移之前把前缀和加上。

对于客户

接客户的单子,可用的内核数量会减少,但会收获钱。那么接后相对于接前少了 $c_i$ 个内核,但钱增加了 $v_i$,所以结果表达式如下:

那状态转移方程就是这样:


滚动数组

开二维数组空间不够,于是自然想到了让数组打滚。然而,滚起来之后,$j$ 到底该从小到大还是从大往小?

这个顺序只取决于一个因素,就是这个状态转移方程所使用的 $dp$ 值在需要求的值的前面还是后面。如果在前面,就需要倒着枚举,如果在后面,就要正着枚举,以保证利用的是本来为 $dp_{i-1,?}$ 而非 $dp_{i,?}$。

所以,处理购买计算机的请求要从大到小枚举,处理客户单子需要从小到大枚举。

注意一下初始值,数组赋极小值,$dp_{0}=0$。

1
2
3
4
5
6
7
8
9
10
for(int i = 1; i <= num; i++) {
if(!a[i].data) { // 计算机
C += a[i].c;
for(int j = C; j >= a[i].c; j--)
dp[j] = std :: max(dp[j], dp[j - a[i].c] - a[i].v);
} else { // 客户
for(int j = 0; j <= C - a[i].c; j++)
dp[j] = std :: max(dp[j], dp[j + a[i].c] + a[i].v);
}
}

求答案

非常简单,长这样:

注意,$i$ 的初始值为 $0$。

我最开始做的时候以为这个地方初始值是 $1$,因为 $ans$ 初始值就是 $0$ 嘛!于是喜提 $\text{18pts}$……

其实最终 $dp_0$ 不一定是没有购买计算机,也有可能是内核数量刚好消耗完

Peter:这其实就和牛顿第一定律一样嘛,要么不受外力,要么合力为零,两种情况嘛。

我承认你说得很有道理,但是你是物理学疯了?


Code

不开 long long 见祖宗。

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
50
51
52
53
54
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

const int maxn = (int) 2e5 + 5;

struct node { int c, f, v; bool data; } a[4005];
int C, n, m, num, ans, dp[maxn];

bool cmp(node x, node y) {
if(x.f != y.f)
return x.f > y.f;
if(x.data != y.data)
return x.data < y.data;
if(!x.data)
return x.v < y.v;
return x.v > y.v;
}

signed main() {
memset(dp, -0x3f, sizeof(dp));
dp[0] = 0;
scanf("%lld", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld %lld %lld", &a[i].c, &a[i].f, &a[i].v);
a[i].data = 0;
}
scanf("%lld", &m);
for(int i = n + 1; i <= n + m; i++) {
scanf("%lld %lld %lld", &a[i].c, &a[i].f, &a[i].v);
a[i].data = 1;
}
num = m + n;
std :: stable_sort(a + 1, a + num + 1, cmp);
/*
for(int i = 1; i <= num; i++)
printf("%d %d %d %d\n", a[i].c, a[i].f, a[i].v, a[i].data);
*/
for(int i = 1; i <= num; i++) {
if(!a[i].data) { // 计算机
C += a[i].c;
for(int j = C; j >= a[i].c; j--)
dp[j] = std :: max(dp[j], dp[j - a[i].c] - a[i].v);
} else { // 客户
for(int j = 0; j <= C - a[i].c; j++)
dp[j] = std :: max(dp[j], dp[j + a[i].c] + a[i].v);
}
}
for(int i = 0; i <= C; i++)
ans = std :: max(ans, dp[i]);
printf("%lld", ans);
return 0;
}

AC 记录