有一说一，华子这次的题真的难！

1、动态规划（100%）

将起点看成0，中间有n块板子，终点为n+1,。有一个初始生命数，有些点的板子是空的，走到上面就会减1条生命。题目求从点0到点n+1的方案数。

public class Main {
    static boolean[] absent;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        absent = new boolean[n + 2];
        for (int i = 0; i < k; i++) {
            int t = scanner.nextInt();
            absent[t] = true;
        }
        // dp[i][j]：从起点到点i，剩余j条命的走法
        int[][] dp = new int[n + 2][m + 1];
        dp[0][m] = 1;
        // 当前点i
        for (int i = 1; i < n + 2; i++) {
            // 当前点木板缺失，需要在后续的计算中减一条生命值
            int lose = absent[i] ? -1 : 0;
            // 可由前面的点x而来
            for (int x = i - 1; x >= Math.max(i - 3, 0); x--) {
                // 前面点的命
                for (int j = 1; j < m + 1; j++) {
                    dp[i][j + lose] += dp[x][j];
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < m + 1; i++) {
            ans += dp[n + 1][i];
        }
        System.out.println(ans);
    }
}

2、贪心+暴力（100%）

这道题在做的时候贪心可以AC，但可能是测试数据太弱了。评论区有大佬列出了贪心不能过的测试用例，所以这道题用贪心是有问题的。

但是我们还是可以学习一下贪心思路，具体可看【LC会议室Ⅱ】这道题，思路几乎一样。n个任务和m个可完成任务的容器，就完成这些任务所需的最小时间。
这道题贪了三个地方：

1. 数据按照传输时间逆序排序，先处理传输时间最长的；
2. 在满足传输条件的所有通道里，优先选取最早空闲的（即最早完成自己通道内传输任务的），这样可以最小限度地增加通道的处理时间；
3. 如果最早空闲时间也相同，就选取传输能力最小的，将能力大的留给后面的任务。

   public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        // 通道数
        int n = scanner.nextInt();
        // [通道传输能力][空闲时间]
        int[][] channels = new int[n][2];
        for (int i = 0; i < n; i++) {
            channels[i][0] = scanner.nextInt();
        }
        int[][] data = new int[m][2];
        for (int i = 0; i < m; i++) {
            // 大小
            data[i][0] = scanner.nextInt();
        }
        for (int i = 0; i < m; i++) {
            // 传输时长
            data[i][1] = scanner.nextInt();
        }
        // 按传输时长逆序
        Arrays.sort(data, (a, b) -> {
            if (a[1] == b[1]) {
                return a[0] - b[0];
            }
            return b[1] - a[1];
        });
        // 贪心1
        for (int[] d : data) {
            int minIdleTime = Integer.MAX_VALUE;
            int ch = 0;
            // 遍历每个通道
            for (int i = 0; i < n; i++) {
                // 需要满足传输条件
                if (channels[i][0] >= d[0]) {
                    // 贪心2
                    if (channels[i][1] < minIdleTime) {
                        ch = i;
                        minIdleTime = channels[i][1];
                    } else if (channels[i][1] == minIdleTime && channels[i][0] < channels[ch][0]) {
                        // 贪心3
                        ch = i;
                    }
                }
            }
            channels[ch][1] += d[1];
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, channels[i][1]);
        }
        System.out.println(max);
    }
   }

   3、带TTL的最短路径算法（0%，直接不会）

   出一个朴素版的最短路径我都不一定能写出来，结果还带一个额外条件TTL，我还看到了允许的运行时间很苛刻，Java都只有800ms，我都把图建起来了，还是没有写下去的勇气！

考完后我同学说最后输出-1竟然可以过19%，57分啊！（心痛！）