釣魚（資訊學奧賽一本通-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;
}