1431：钓鱼

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

【输入】

【输出】

【输入样例】

3
1
4 5 6
1 2 1
1 2

【输出样例】

35

【提示】

解析： 

依次枚举在前i个湖中钓鱼的情况；

先减掉路上消耗的时间；

选这i个湖中5分钟可以钓最多的鱼的湖钓5分钟，然后更新这个湖5分钟可以钓鱼的数量；

直到时间消耗光；

使用优先队列维护可钓鱼的湖；

详见代码：

#include<bits/stdc++.h>
using namespace std;
int H,n;
int t;//分钟数
int a[105];//a[i]表示第i个湖第1个5分钟可以钓到鱼的数量
int d[105];//d[i]表示第i个湖每5分钟钓鱼的减少数量
int T[105];//T[i]表示从第i个湖到第i+1个湖所用的时间为5*T[i]
struct node{
    int a;//当前5分钟可以钓鱼数量
    int d;//每5分钟减少数量
    //重置小于号运算符，钓鱼数量小的小
    bool operator < (const node &x) const{
        return a<x.a;
    }
};
priority_queue <node> q;//大根堆
int ans=0;
int main() {
    cin>>n>>H;
    t=H*60;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>d[i];
    }
    for(int i=1;i<n;i++){
        cin>>T[i];
    }
    for(int i=1;i<=n;i++){//枚举钓鱼的湖的数量
        int t1=t;//时间
        for(int j=1;j<i;j++){//去掉走路用的时间
            t1-=T[j]*5;
        }
        while(!q.empty()){//清空优先队列
            q.pop();
        }
        for(int j=1;j<=i;j++){//枚举每个鱼塘
            node x;
            x.a=a[j];//当前鱼塘5分钟可以钓鱼数量
            x.d=d[j];//每5分钟减少数量
            q.push(x);
        }
        int sum=0;//钓鱼数量
        while (t1>=5){//只要时间大于等于5分钟，就可以钓鱼
            if (!q.empty()){//还有鱼塘可以钓到鱼
                node x=q.top();//捡最多的钓
                sum+=x.a;//钓鱼数量
                t1-=5;//消耗5分钟
                q.pop();//钓完弹出
                x.a-=x.d;//计算这个鱼塘下五分钟可以钓鱼数量
                if (x.a>0){//如果数量大于0
                    q.push(x);//加入优先队列
                }
            }else{//如果没有能钓到鱼的鱼塘，退出循环
                break;
            }
        }
        ans=max(ans,sum);//取最大值
    }
    cout<<ans;
    return 0;
}