六 1262. 鱼塘钓鱼 (多路归并)

1262. 鱼塘钓鱼 (多路归并)

思路：遍历最远到的鱼塘，同时将截止时间减去路上花的时间，然后多路归并，不考虑具体钓鱼的顺序，每次都调最多的鱼。

import java.util.*;

public class Main {
    private static int[] a;
    private static int[] b;
    private static int[] c;
    private static int[] d;
    
    private static int get(int k) {
        return Math.max(0, a[k] - b[k] * d[k]);
    }
    
    private static int work(int n, int T) {
        int res = 0;
        d = new int[n + 1];
        for (int i = 0; i < T; i++) {
            int t = 1;
            for (int j = 2; j <= n; j++) {
                if (get(t) < get(j)) {
                    t = j;
                }
            }
            res += get(t);
            d[t]++;
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a = new int[n + 1];
        b = new int[n + 1];
        c = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            b[i] = sc.nextInt();
        }
        for (int i = 2; i <= n; i++) {
            c[i] = sc.nextInt();
            c[i] += c[i - 1];
        }
        int T = sc.nextInt();
        
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, work(i, T - c[i]));
        }
        System.out.println(res);
    }
}