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

题目

有 N个鱼塘排成一排，每个鱼塘中有一定数量的鱼，例如：N=5时，如下表：
在这里插入图片描述
即：在第 1个鱼塘中钓鱼第 1分钟内可钓到 10条鱼，第 2分钟内只能钓到 8条鱼，……，第 5分钟以后再也钓不到鱼了。

从第 1个鱼塘到第 2个鱼塘需要 3分钟，从第 2个鱼塘到第 3个鱼塘需要 5分钟，……

给出一个截止时间 T，设计一个钓鱼方案，从第 1个鱼塘出发，希望能钓到最多的鱼。

假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

输入格式

共 5行，分别表示：

第1行为 N；

第2行为第 1分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；

第3行为每过 1分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；

第4行为当前鱼塘到下一个相邻鱼塘需要的时间；

第5行为截止时间 T。

输出格式

一个整数（不超过231−1），表示你的方案能钓到的最多的鱼。

数据范围

1≤N≤100

1≤T≤1000

输入样例：

5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14

输出样例：

题解

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author akuya
 * @create 2024-03-15-18:58
 */
public class Main {
    static int n;
    static int N=101;
    static int T;
    static int a[]=new int[N];
    static int d[]=new int[N];
    static int l[]=new int[N];
    static int spend[]=new int[N];
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=1;i<=n;i++){
            a[i]=scanner.nextInt();
        }
        for(int i=1;i<=n;i++){
            d[i]=scanner.nextInt();
        }
        for(int i=2;i<=n;i++){
            l[i]=scanner.nextInt();
            l[i]+=l[i-1];
        }
        T=scanner.nextInt();
        int res=0;
        for(int i=1;i<=n;i++){
            res=Math.max(res,work(i,T-l[i]));
        }

        System.out.println(res);
    }

    public static int work(int a,int b){
        int res=0;
        Arrays.fill(spend,0);
        for(int i=0;i<b;i++){
            int t=1;
            for(int j=2;j<=a;j++){
                if (get(t) < get(j)) {
                    t=j;
                }
            }
            res+=get(t);
            spend[t]++;
        }

        return res;
    }

    public static int get(int i){
        return Math.max(a[i]-d[i]*spend[i],0);
    }
}