9.14 华为笔试（华子这次有点狠）

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

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个可完成任务的容器，就完成这些任务所需的最小时间。
这道题贪了三个地方：

数据按照传输时间逆序排序，先处理传输时间最长的；
在满足传输条件的所有通道里，优先选取最早空闲的（即最早完成自己通道内传输任务的），这样可以最小限度地增加通道的处理时间；

如果最早空闲时间也相同，就选取传输能力最小的，将能力大的留给后面的任务。

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);
 }
}