一、题目描述
共有N块能量石, 小怪兽肚子里只能有一块能量石, 消化完后才能吃下一块
第$\ i\ $块能量石, 需要$\ S_i\ $秒消化完, 蕴含的能量为$\ E_i\ $, 每秒失去的能量为$\ L_i\ $ (从程序开始运行,所有的能量石就开始减少能量)
能量石的能量会直接被小怪兽吸收, 每块能量石的能量最多下降到 0,不会有额外能量损失
求解小怪兽可以获取能量的最大值
二、分析
1. 模型
- 与朴素的01背包之间不同处在于, 价值会随时间损失,且每个物品每秒的损失不同
- 解空间范围大,通过贪心策略发掘题目中的性质,缩小最优解空间
2. 性质
-
性质1
设最优解中,花费的总时间为$\ t \ $,若第$\ i\ $块能量石的能量已经为0,即$E_i - t \times L_i \leq 0$,则为无效能量石,一定不在最优解中 -
性质2
设最优解中,共有$\ K \ $块有效石头($1 \leq K \leq N$)
则对任意有效能量石有$E_k - t \times L_k > 0$ -
性质3:
设吃某块能量石时,已经过去了$\ t \ $秒,则任意魔法石经过损失的能量为$\ E_k’ = E_k - t \times L_k $,
最优解中相邻两块能量石邻项交换后所得能量满足下列不等式
$E_k’ + E_{k+1}’ - S_k · L_{k+1} \ \ \geq\ \ E_k’ + E_{k+1}’ - S_{k+1} · L_k$
若满足上列不等式,则$S_k · L_{k+1} \ \leq\ S_{k+1} · L_k$,即$ \frac{S_k}{L_k} \ \ \leq \ \ \frac{S_{k+1}}{L_{k+1}}$
综上,依据S和L和比值升序排序的顺序吃
3. DP分析
-
状态表示$f(i,\ j)$
从前$\ i\ $个物品中选,恰好过去$\ j\ $单位时间的所有选法的集合,记录最大值 -
状态计算:
不选第$\ i\ $个物品:f[i - 1][j]
选第$\ i\ $个物品:f[i -1][j - s] + e - (j - s) * l
三、java代码
import java.util.Scanner;
import java.util.Arrays;
public class Main {
static final int N = 10010;
static Stone[] stone = new Stone[N];
static int[] f = new int[N];
static int n, m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int C = 1; C <= T; C++) {
n = sc.nextInt();
m = 0;
for (int i = 0; i < n; i++) {
int s = sc.nextInt();
int e = sc.nextInt();
int l = sc.nextInt();
stone[i] = new Stone(s, e, l);
m += s;
}
// 依据S和L的比值排序...
Arrays.sort(stone, 0, n);
// 能量的损失与时间成正比,状态表示中的j是确定值
Arrays.fill(f, -1);
f[0] = 0;
for (int i = 0; i < n; i++) {
int s = stone[i].s, e = stone[i].e, l = stone[i].l;
for (int j = m; j >= s; j--) {
f[j] = Math.max(f[j], f[j - s] + Math.max(0, e - (j - s) * l));
}
}
int res = -1;
for (int i = 0; i <= m; i++) res = Math.max(res, f[i]);
System.out.printf("Case #%d: %d\n", C, res);
}
}
static class Stone implements Comparable<Stone> {
int s, e, l;
Stone(int s, int e, int l) {
this.s = s;
this.e = e;
this.l = l;
}
@Override
public int compareTo(Stone t) {
// l可能为0, 故不写成s / l - t.s / t.l
return s * t.l - t.s * l;
}
}
}