|
|
##[$AcWing$ $734$. 能量石](https://www.acwing.com/problem/content/description/736/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
岩石怪物 **杜达** 生活在魔法森林中，他在午餐时收集了 $N$ 块能量石准备开吃。
|
|
|
|
|
|
由于他的嘴很小，所以一次只能吃一块能量石。
|
|
|
|
|
|
能量石很硬，吃完需要花不少时间。
|
|
|
|
|
|
吃完第 $i$ 块能量石需要花费的时间为 $S_i$ 秒。
|
|
|
|
|
|
杜达靠吃能量石来获取能量。
|
|
|
|
|
|
不同的能量石包含的能量可能不同。
|
|
|
|
|
|
此外，能量石会随着时间流逝逐渐失去能量。
|
|
|
|
|
|
第 $i$ 块能量石最初包含 $E_i$ 单位的能量，并且每秒将失去 $L_i$ 单位的能量。
|
|
|
|
|
|
当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。
|
|
|
|
|
|
能量石中包含的能量最多降低至 $0$。
|
|
|
|
|
|
请问杜达通过吃能量石 <font color='red' size=4><b>可以获得的最大能量是多少？</b></font>
|
|
|
|
|
|
**输入格式**
|
|
|
第一行包含整数 $T$，表示共有 $T$ 组测试数据。
|
|
|
|
|
|
每组数据第一行包含整数 $N$，表示能量石的数量。
|
|
|
|
|
|
接下来 $N$ 行，每行包含三个整数 $S_i,E_i,L_i$。
|
|
|
|
|
|
**输出格式**
|
|
|
每组数据输出一个结果，每个结果占一行。
|
|
|
|
|
|
结果表示为 `Case #x: y`，其中 `x` 是组别编号（从 `1` 开始），`y` 是可以获得的最大能量值。
|
|
|
|
|
|
**数据范围**
|
|
|
$1≤T≤10,1≤N≤100,1≤S_i≤100,1≤E_i≤10^5,0≤L_i≤10^5$
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
3
|
|
|
4
|
|
|
20 10 1
|
|
|
5 30 5
|
|
|
100 30 1
|
|
|
5 80 60
|
|
|
3
|
|
|
10 4 1000
|
|
|
10 3 1000
|
|
|
10 8 1000
|
|
|
2
|
|
|
12 300 50
|
|
|
5 200 0
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
Case #1: 105
|
|
|
Case #2: 8
|
|
|
Case #3: 500
|
|
|
```
|
|
|
|
|
|
**样例解释**
|
|
|
在样例＃$1$中，有 $N=4$ 个宝石。杜达可以选择的一个吃石头顺序是：
|
|
|
|
|
|
- 吃第四块石头。这需要 $5$ 秒，并给他 $80$ 单位的能量。
|
|
|
- 吃第二块石头。这需要 $5$ 秒，并给他 $5$ 单位的能量（第二块石头开始时具有 $30$ 单位能量，$5$ 秒后失去了 $25$ 单位的能量）。
|
|
|
- 吃第三块石头。这需要 $100$ 秒，并给他 $20$ 单位的能量（第三块石头开始时具有 $30$ 单位能量，$10$ 秒后失去了 $10$ 单位的能量）。
|
|
|
- 吃第一块石头。这需要 $20$ 秒，并给他 $0$ 单位的能量（第一块石头以 $10$ 单位能量开始，$110$ 秒后已经失去了所有的能量）。
|
|
|
|
|
|
他一共获得了 $105$ 单位的能量，这是能获得的最大值，所以答案是 $105$。
|
|
|
|
|
|
在样本案例＃$2$中，有 $N=3$ 个宝石。
|
|
|
|
|
|
无论杜达选择吃哪块石头，剩下的两个石头的能量都会耗光。
|
|
|
|
|
|
所以他应该吃第三块石头，给他提供 $8$ 单位的能量。
|
|
|
|
|
|
在样本案例＃$3$中，有 $N=2$ 个宝石。杜达可以：
|
|
|
|
|
|
- 吃第一块石头。这需要$12$ 秒，并给他 $300$ 单位的能量。
|
|
|
- 吃第二块石头。这需要 $5$ 秒，并给他 $200$ 单位的能量（第二块石头随着时间的推移不会失去任何能量！）。
|
|
|
所以答案是 $500$。
|
|
|
|
|
|
### 二、贪心（微扰）
|
|
|
|
|
|
#### 1、贪心+$DP$
|
|
|
|
|
|
此题与普通的$01$背包是不同的，$01$背包不强调 **每个物品的顺序**，但本题物品在前和在后是不一样的问题：因为能量石会 **逐渐失去能量**！，随着时间的进行， 不同的摆放顺序会造成结果不同！
|
|
|
|
|
|
|
|
|
#### 2、集合角度思考
|
|
|
求某个集合的最优解，求所有不同的吃法的最优解。这里的不同有两个维度:
|
|
|
* 按什么样的顺序吃
|
|
|
* 选择吃哪些能量石
|
|
|
|
|
|
|
|
|
本身是 **两维变化** ，不好做，哪些，顺序都需要关注，所以从题目中挖掘了一些性质，通过 **贪心** 简化后，再去动态规划。
|
|
|
|
|
|
#### 3、思考过程
|
|
|
为何要先进行贪心呢，或者说贪心的必要性是什么？
|
|
|
其 实你有 耍 **[国王游戏](https://www.cnblogs.com/littlehb/p/15038424.html)**, **[耍杂技的牛](https://www.cnblogs.com/littlehb/p/15488847.html)** 的训练，你就会明白，其实顺序很重要，按什么样的顺序来进行枚举，这需要用 微扰法 证明出一个表达式，有了顺序后，就简单了。
|
|
|
|
|
|
#### 4、贪心微扰（**邻项交换**）证法
|
|
|
例题：
|
|
|
|
|
|
**[国王游戏](https://www.cnblogs.com/littlehb/p/15038424.html)**
|
|
|
|
|
|
**[耍杂技的牛](https://www.cnblogs.com/littlehb/p/15488847.html)**
|
|
|
|
|
|
|
|
|
假定当前所选的能量石为$k$个，考虑怎样的排列是最优的。
|
|
|
|
|
|
对于任一排列$$\LARGE a_1,a_2,a_3,…a_k$$
|
|
|
|
|
|
考虑任意 <font color='red' size=4><b>相邻两项</b> </font>$\LARGE a_i,a_{i+1}$,其交换后，不影响其他能量石的收益
|
|
|
|
|
|
<font color='red' size=4><b>假定收集完第$i−1$块能量石时是第$k$秒</b></font> ，考虑交换前和交换后的收益：令$j=i+1$以方便下面的书写:
|
|
|
|
|
|
**交换前：**
|
|
|
$$\large E_i−kL_i+E_j−(k+S_i)L_j=E_i+E_j−(kL_i+(k+S_i)L_j) \ ①$$
|
|
|
|
|
|
|
|
|
> **解释**:
|
|
|
> - $E_i$:吃掉第$i$个能量石，立刻获取到$E_i$个能量
|
|
|
> - $-kL_i$:从开始到吃到第$i$个时，经过了$k$秒，那么，第$i$件能量石已经消耗掉了$k \times L_i$
|
|
|
> - $E_j$:吃掉第$i+1$个能量石，立刻获取到$E_j$个能量
|
|
|
> - $-(k+S_i)\times L_j$:在吃第$i+1$个之前，又经历了一个$i$号能量石，多等待了$S_i$秒，总的时长就是$k+S_i$,再剩以第$i+1$个能量石的能量损耗速度$L_j$,就是第$i+1$号能量石的损耗能量。
|
|
|
|
|
|
**交换后：**
|
|
|
$$\large E_j−kL_j+E_i−(k+S_j)L_i=E_i+E_j−(kL_j+(k+S_j)L_i) \ ②$$
|
|
|
|
|
|
|
|
|
如果原方案最佳，则有 ① >= ②
|
|
|
|
|
|
$$\large E_i+E_j−(kL_i+(k+S_i)L_j) >= E_i+E_j−(kL_j+(k+S_j)L_i)$$
|
|
|
|
|
|
$$\large −(kL_i+(k+S_i)L_j) >= −(kL_j+(k+S_j)L_i)$$
|
|
|
|
|
|
$$\large (kL_i+(k+S_i)L_j) <= (kL_j+(k+S_j)L_i)$$
|
|
|
|
|
|
$$\large \therefore S_iL_j<=S_jL_i$$
|
|
|
|
|
|
|
|
|
### 三、$01$背包
|
|
|
|
|
|
背包问题有三种形态：**[至多/恰好/至少](https://www.cnblogs.com/littlehb/p/15732285.html)** ,本题是哪种呢？
|
|
|
|
|
|
因为在不同时刻吃所能吸收的能量是不同的，而且每块能量石从最开始就在损失能量。所以能量的价值和时间是相关的，如果剩余空间长大，未必就一定划算，这就说明剩余空间需要一个精确值，而不能表示一个范围，所以是 <font color='red' size=5><b>恰好</b></font>。
|
|
|
|
|
|
* 占用的空间：$q[i].s$
|
|
|
|
|
|
* 获得的价值:$max(0, q[i].e - (j - q[i].s) * q[i].l)$ ($j$为当前花费时长)。
|
|
|
|
|
|
#### 状态表示
|
|
|
$f[j]$ : 当前 **恰好** 花$j$时间得到的最大能量
|
|
|
|
|
|
#### 状态转移方程
|
|
|
|
|
|
$f[j] = max(f[j], f[j - q[i].s] + max(0, q[i].e - (j - q[i].s) * q[i].l))$
|
|
|
|
|
|
由于我们背包放物品（宝石）的顺序是坐标从$1$到$n$的，所以一定能枚举到最优解。
|
|
|
|
|
|
初始状态：$f[0]=0$，其余为负无穷(因为是求最大值)
|
|
|
|
|
|
答案：$max(f[i])$
|
|
|
|
|
|
### 四、二维版本
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 110;
|
|
|
const int M = 10010;
|
|
|
|
|
|
int n;
|
|
|
struct Node {
|
|
|
int s; // 吃掉这块能量石需要花费的时间为s秒
|
|
|
int e; // 获得e个能量
|
|
|
int l; // 不吃的话，每秒失去l个能量
|
|
|
const bool operator<(const Node &b) const {
|
|
|
return s * b.l < b.s * l; // 结构体对比函数
|
|
|
}
|
|
|
} q[N]; // 能量石的数组
|
|
|
|
|
|
int f[N][M];
|
|
|
|
|
|
int idx; // 输出是第几轮的测试数据
|
|
|
|
|
|
int main() {
|
|
|
int T;
|
|
|
scanf("%d", &T);
|
|
|
while (T--) {
|
|
|
scanf("%d", &n);
|
|
|
int m = 0; // 能量视为体积
|
|
|
int res = 0; // 记录最大值
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
scanf("%d %d %d", &q[i].s, &q[i].e, &q[i].l);
|
|
|
m += q[i].s; // 极限容量，做为背包的上限
|
|
|
}
|
|
|
// 排序
|
|
|
sort(q + 1, q + 1 + n);
|
|
|
// 每次清空状态数组
|
|
|
memset(f, 0, sizeof f);
|
|
|
|
|
|
// 二维01背包
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
int l = q[i].l, s = q[i].s, e = q[i].e;
|
|
|
for (int j = 0; j <= m; j++) {
|
|
|
f[i][j] = f[i - 1][j]; // 如果不要物品i
|
|
|
if (j >= s) // 如果可以要物品i
|
|
|
f[i][j] = max(f[i - 1][j], f[i - 1][j - s] + max(0, e - (j - s) * l));
|
|
|
res = max(res, f[i][j]);
|
|
|
}
|
|
|
}
|
|
|
cout << "Case #" << ++idx << ": " << res << endl;
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 五、一维版本
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 110; // 能量石个数上限
|
|
|
const int M = 10010; // 能量上限
|
|
|
|
|
|
// 用来描述每个能量石的结构体
|
|
|
struct Node {
|
|
|
int s; // 吃掉这块能量石需要花费的时间为s秒
|
|
|
int e; // 可以获利e个能量
|
|
|
int l; // 不吃的话，每秒失去l个能量
|
|
|
} q[N]; // 能量石的数组
|
|
|
|
|
|
// 结构体对比函数
|
|
|
bool cmp(const Node &a, const Node &b) {
|
|
|
return a.s * b.l < b.s * a.l;
|
|
|
}
|
|
|
|
|
|
int n; // 能量石的数量
|
|
|
int f[M]; // f[i]:花i个时间得到的最大能量
|
|
|
int idx; // 输出是第几轮的测试数据
|
|
|
|
|
|
int main() {
|
|
|
// T组测试数据
|
|
|
int T;
|
|
|
scanf("%d", &T);
|
|
|
|
|
|
while (T--) {
|
|
|
// 初始化为负无穷,预求最大，先设最小
|
|
|
memset(f, -0x3f, sizeof f);
|
|
|
|
|
|
scanf("%d", &n);
|
|
|
// 总时长,背包容量
|
|
|
int m = 0;
|
|
|
int res = 0;
|
|
|
// 读入数据
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
scanf("%d %d %d", &q[i].s, &q[i].e, &q[i].l);
|
|
|
m += q[i].s;
|
|
|
}
|
|
|
// 贪心排序
|
|
|
sort(q + 1, q + 1 + n, cmp);
|
|
|
|
|
|
// 01背包,注意恰好装满时的状态转移方程的写法
|
|
|
// 不能是至多j,而是恰好j
|
|
|
// 这是因为如果时间越长，不见得获取的能量越多，因为能量石会损耗掉
|
|
|
// 恰好的，最终需要在所有可能的位置去遍历一次找出最大值
|
|
|
// 每次清空状态数组
|
|
|
memset(f, 0, sizeof f);
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
int e = q[i].e, s = q[i].s, l = q[i].l;
|
|
|
for (int j = m; j >= s; j--) {
|
|
|
int w = e - (j - s) * l;
|
|
|
f[j] = max(f[j], f[j - s] + w);
|
|
|
res = max(res, f[j]);
|
|
|
}
|
|
|
}
|
|
|
printf("Case #%d: %d\n", ++idx, res);
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
