思路

1. 全靠嫖，大佬还是大佬，指路AcWing 734. 能量石
2. 贪心
   • 有的石头可能耗时s短、能量e高但是损耗速度l快，前几个石头吃完这个石头的能量就流失光了，所以这类石头应该时越早吃越好。但也不能直接跳过前面的石头，万一这个石头排在最后呢。。
   • 多个石头之间怎么确定优先级呢？科学的说法在上面那篇题解里，这里就记下自己的理解。
     1. 假设按顺序当前选中了第$i$个石头，下一个石头就是第$i+1$个。吃第$i$个石头所需时间为$S_i$，而下个石头损耗速度为$L_{i+1}$，那么损耗的能量为$\Delta E_1 = S_i * L_{i+1}$
     2. 如果改为先吃第$i+1$个，再吃第$i$个。吃第$i+1$个石头所需时间为$S_{i+1}$，而下个石头损耗速度为$L_{i}$，那么损耗的能量为$\Delta E_2 = S_{i+1} * L_{i}$
     3. 显然，对于相邻两个石头，先吃$\Delta E$较小的，再吃另一个，最终获得的能量会更多。即若$\Delta E_1 < \Delta E_2$，先吃$i$再吃$i+1$，反之则顺序调换
     4. 同理，将石头个数从2拓展到n，同样按$\Delta E$从小到大的顺序吃，所以考虑以$\Delta E = S_i * L_j$作为指标进行排序
3. 每个石头只能被吃一次，所以01背包，容量（最大总耗时）为$\sum^{i=n}_{i=1}S_i$，石头的能量与当前时间有函数关系$E_{now} = E_{start} - t_{now} * L$
   • $f(i,j)$表示只考虑前$i$个物品且总耗时恰好为$j$的选法集合，属性为$Max$，状态计算为$f(i, j) = max(f(i-1, j), f(i-1, j-S_i)+E_{now})$
     • 为什么是“恰好”？我也说不清，烦请指正。移步大佬题解评论区，大致意思就是耗时会影响石头的能量，可能导致耗时增加但总能量反而减少···blablabla
   • 本着能用就行，略过上个点，属性$Max$所以初始值设置为一个极小的数,f[i][j]=Integer.MIN_VALUE
   • 不吃任何石头且耗时为0时，获得的最大能量为0，所以f[0][0]=0
   • 也因为是“恰好”，所以f[n][timeMax]不一定是最优解，要遍历所有“只考虑前n个石头”的最终解，取最大值

代码 二维

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static class Stone {
        public int s, e, l;

        public Stone(int s, int e, int l) {
            this.s = s;
            this.e = e;
            this.l = l;
        }

        // 传入要吃的时刻 返回改时刻的能量
        public int getENow(int timeNow) {
            return Math.max(0, e - timeNow * l);
        }
    }

    static int t, n;
    static int[][] f = new int[110][10010];  // 存状态
    static Stone[] stones = new Stone[110];  // 存石头

    public static void main(String[] args) {
        t = scanner.nextInt();
        for (int k = 1; k <= t; k++) {
            n = scanner.nextInt();
            // 统计最大耗时 -- 所有石头都吃的情况 耗时累加
            int timeMax = 0;
            for (int i = 1; i <= n; i++) {
                stones[i] = new Stone(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
                timeMax += stones[i].s;
            }
            // 按损耗能量升序排列
            Arrays.sort(stones, 1, n + 1, (o1, o2) -> o1.s * o2.l - o2.s * o1.l);
            // 属性取Max 初始值设置为负无穷
            for (int i = 0; i <= n; i++) {
                Arrays.fill(f[i], Integer.MIN_VALUE);
            }
            // 初始化边界
            f[0][0] = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= timeMax; j++) {
                    f[i][j] = f[i - 1][j];
                    if (j >= stones[i].s) {
                        f[i][j] = Math.max(f[i][j], f[i - 1][j - stones[i].s] + stones[i].getENow(j - stones[i].s));
                    }
                }
            }
            // 遍历f[n][·]取最大值
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i <= timeMax; i++) {
                ans = Math.max(ans, f[n][i]);
            }
            System.out.printf("Case #%d: %d\n", k, ans);
        }
    }
}

代码 一维

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static class Stone {
        public int s, e, l;

        public Stone(int s, int e, int l) {
            this.s = s;
            this.e = e;
            this.l = l;
        }

        public int getENow(int timeNow) {
            return Math.max(0, e - timeNow * l);
        }
    }

    static int t, n;
    static int[] f = new int[10010];
    static Stone[] stones = new Stone[110];

    public static void main(String[] args) {
        t = scanner.nextInt();
        for (int k = 1; k <= t; k++) {
            n = scanner.nextInt();
            int timeMax = 0;
            for (int i = 1; i <= n; i++) {
                stones[i] = new Stone(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
                timeMax += stones[i].s;
            }
            Arrays.sort(stones, 1, n + 1, (o1, o2) -> o1.s * o2.l - o2.s * o1.l);
            Arrays.fill(f, Integer.MIN_VALUE);
            f[0] = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = timeMax; j >= stones[i].s; j--) {
                    f[j] = Math.max(f[j], f[j - stones[i].s] + stones[i].getENow(j - stones[i].s));
                }
            }
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i <= timeMax; i++) {
                ans = Math.max(ans, f[i]);
            }
            System.out.printf("Case #%d: %d\n", k, ans);
        }
    }
}