信息学奥赛一本通T1431：钓鱼

【题目描述】

在一条水平路边，有 nn 个钓鱼湖，从左到右编号为 1,2,…,n。佳佳有 HH 个小时的空余时间，他希望利用这个时间钓到更多的鱼。他从 1 出发，向右走，有选择的在一些湖边停留一定的时间（是 55 分钟的倍数）钓鱼。最后在某一个湖边结束钓鱼。佳佳从第 i 个湖到第 i+1 个湖需要走 5×Ti分钟路，还测出在第 i 个湖停留，第一个 5 分钟可以钓到 Fi​​ 条鱼，以后每再钓 5 分钟，可以钓到的鱼量减少 Di​​ ，若减少后的鱼量小于 0，则减少后的鱼量为 0 。为了简化问题，佳佳假定没有其他人钓鱼，也没有其他因素影响他钓到期望数量的鱼。请编程求出佳佳最多能钓鱼的数量。

【输入】

第一行一个整数 n，表示湖的个数

第二行一个整数 H，表示佳佳的空闲时间

第三行有 n 个整数，依次表示每个湖第一个 5 分钟能钓到鱼的数量

第四行有 n 个整数，依次表示以后的每5分钟钓鱼数量比前一个 5 分钟钓鱼数量减少的数量

第五行有 n−1 个整数，Ti 表示由第 i 个湖到第 i+1 个湖需要花 5×Ti分钟的路程

【输出】

输出只有一行，表示佳佳最多能钓鱼的数量。

【输入样例】

3
1
4 5 6
1 2 1
1 2

【输出样例】

35

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
int fish[N],d[N],t[N];
priority_queue<pair<int,int> > Q;
int main(){
    int n,h;
    scanf("%d%d",&n,&h);
    h*=60;
    for(int i=1;i<=n;i++)
        scanf("%d",&fish[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&d[i]);
    for(int i=1;i<=n-1;i++)
        scanf("%d",&t[i]);

    int walkTime=0;
    int maxx=-INF;
    for(int i=1;i<=n;i++){//可到达的池塘
        int restTime=h-walkTime;
        int res=0;

        for(int j=1;j<=i;j++)
            Q.push(make_pair(fish[j],j));
        while(restTime>0&&Q.top().first>0){//选鱼最多的池塘
            pair<int,int> temp=Q.top();
            Q.pop();

            res+=temp.first;
            temp.first-=d[temp.second];
            Q.push(temp);
            restTime-=5;
        }
        maxx=max(maxx,res);
        walkTime+=t[i]*5;
    }

    printf("%d\n",maxx);

    return 0;
}

信息学奥赛一本通T1431：贪心算法 钓鱼 归属于 贪心算法，更多同类题解源程序见：贪心算法 和 钓鱼