题目描述

看了这个题目知道大概可以用什么算法，但是没思路不会写这应该怎么办啊
想到了贪心和dp
但是发现dp好难，然后贪心却又不知道应该怎么做
参考了y总的思路发现这，也太简单了吧

原理就是枚举
枚举每一个可能到达的鱼塘的个数x，减去路上消费的时间，那么剩下的时间就是在这x个鱼塘中钓鱼，每一分钟我都选择可以钓上来最多的鱼

在这x个鱼塘中选择每一分钟之内可以调上的鱼的数目的最大值，这个时候采用多路归并排序
可以采用堆排序实现，大根堆，采用优先队列实现

最远可以到达的鱼塘有了，那么队列里面怎么添加元素呢？
不可能在第一分钟的时候遍历一遍找到一个最大值，第二种在遍历一边
那就是直接把1-x个鱼塘的鱼的数目都加进来，进行一个堆排序，然后每一次移除一个最大的元素，一直移除dt个
也就是dt分钟

每枚举完可以到达的鱼塘后，选择一个最大值

package tanxin;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class 鱼塘钓鱼 {

    /**
     * @param args
     * @throws IOException 
     * @throws NumberFormatException 
     */
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(bufferedReader.readLine());
        int a[]=new int [1+n];
        int d[]=new int [1+n];
        int t[]=new int [1+n];
        String p[]=bufferedReader.readLine().split(" ");
        for(int i=1;i<=n;i++){
            a[i]=Integer.parseInt(p[i-1]);
        }
          p=bufferedReader.readLine().split(" ");
            for(int i=1;i<=n;i++){
                d[i]=Integer.parseInt(p[i-1]);
            }
        p=bufferedReader.readLine().split(" ");
        for(int i=2;i<=n;i++){
            t[i]=Integer.parseInt(p[i-2]);
            t[i]+=t[i-1];
            //预处理前缀和，在枚举最远可以到达的鱼塘的时候，
            //路途上的时间可以直接计算得到
        }



        int T=Integer.parseInt(bufferedReader.readLine());

        Queue<Integer> queue = new PriorityQueue<Integer>(1100,new Comparator<Integer>() {

            @Override
            public int compare(Integer x, Integer xx) {
                // TODO Auto-generated method stub
                return x-xx>0?-1:1;
            }
        });
        //大根堆
        int ans=0;
        //枚举
        for(int i=1;i<=n;i++){
            int dt=T-t[i];
            int total=0;
            for(int j=1;j<=i;j++){
                for(int k=a[j];k>0;k-=d[j]){
                    queue.add(k);
                }
            }
            while(dt>0 && !queue.isEmpty()){
                total+=queue.poll();
                dt--;
            }
            queue.clear();
            ans=Math.max(ans, total);


        }

        System.out.println(ans);    

    }

}