$$\color{Red}{能量石——融合贪心的01背包}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

证明

这道题首先我们在动态规划前，需要思考一个问题，我们到底该按什么样子的顺序去吃？和以往的背包不同，我们选取物品的先后顺序影响着我们最终的价值总量

类似贪心中推公式的耍杂技的牛

假设我们当前选取的能量石是第i个，相邻的是i+1个
那么此时吃这两个能量石先后顺序的能量和分别为
Ei + Ei+1 - Si * Li+1
Ei+1 + Ei - Si+1 * Li
当我们先吃第i个更合适的时候，满足 Si * Li+1 < Si+1 * Li
那么我们只需要按照Si / Li的顺序进行排序然后再进行动态规划即可
f[i][j]表示正好吃了j秒，在1-i个能量石选择，最大价值的选取方案数
那么我们需要初始化为负无穷，然后最后进行循环判断最大值

java lambda表达式排序（会比直接定义在类中稍微慢一些 几乎可以忽略）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 10010, T, n;
    static int[] f = new int[N];

    static class Node {
        int s, e, l;

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

    static Node[] nodes = new Node[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        int cnt = 0;//第几组
        while (T-- > 0) {
            cnt ++;
            n = Integer.parseInt(br.readLine());
            int m = 0;
            for (int i = 1; i <= n; i++) {
                String[] s1 = br.readLine().split(" ");
                int s = Integer.parseInt(s1[0]);
                int e = Integer.parseInt(s1[1]);
                int l = Integer.parseInt(s1[2]);
                m += s;
                nodes[i] = new Node(s, e, l);
            }
            Arrays.sort(nodes, 1, n+1, (o1, o2) -> Integer.compare(o1.s * o2.l, o2.s * o1.l));
            Arrays.fill(f, -0x3f3f3f3f);
            f[0] = 0;
            for(int i=1; i<=n; i++){
                int s = nodes[i].s;
                int e = nodes[i].e;
                int l = nodes[i].l;

                for(int j=m; j>=s; j--){
                    f[j] = Math.max(f[j], f[j-s] + e - (j-s) * l);
                }
            }
            int res = -1;
            for (int i = 0; i <= m; i++)
                res = Math.max(res, f[i]);
            System.out.println("Case #" + cnt + ": " + res);
        }
    }
}

java 类中重写comparable中的compareTo

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Node implements Comparable<Node>{

    int s, e, l;

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

    @Override
    public int compareTo(Node o) {
        // TODO Auto-generated method stub
        return Integer.compare(this.s * o.l , this.l * o.s);
    }
}

class Main{
    static int N = 10010;
    static Node[] nodes = new Node[N];
    static int[] f = new int[N];

    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        int cnt = 0;

        while(T -- > 0){
            cnt ++;
            int n = Integer.parseInt(in.readLine());
            int m = 0;

            for(int i=1; i<=n; i++){
                String[] cur = in.readLine().split(" ");
                int s = Integer.parseInt(cur[0]);
                int e = Integer.parseInt(cur[1]);
                int l = Integer.parseInt(cur[2]);

                nodes[i] = new Node(s, e, l);
                m += s;
            }

            Arrays.sort(a, 1, n+1);

            Arrays.fill(f, -0x3f3f3f3f);
            f[0] = 0;

            for(int i=1; i<=n; i++){
                int s = nodes[i].s;
                int e = nodes[i].e;
                int l = nodes[i].l;

                for(int j=m; j>=s; j--){
                    f[j] = Math.max(f[j], f[j-s] + 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",cnt, res);
        }
    }
}