【題目描述】

在一條水平路邊，有?nn?個釣魚湖，從左到右編號為 1,2,…,n。佳佳有?HH?個小時的空余時間，他希望利用這個時間釣到更多的魚。他從?1?出發(fā)，向右走，有選擇的在一些湖邊停留一定的時間（是?55?分鐘的倍數(shù)）釣魚。最后在某一個湖邊結(jié)束釣魚。佳佳從第?i?個湖到第?i+1?個湖需要走?5×Ti分鐘路，還測出在第?i?個湖停留，第一個?5?分鐘可以釣到?Fi?? 條魚，以后每再釣?5?分鐘，可以釣到的魚量減少?Di?? ，若減少后的魚量小于?0，則減少后的魚量為?0?。為了簡化問題，佳佳假定沒有其他人釣魚，也沒有其他因素影響他釣到期望數(shù)量的魚。請編程求出佳佳最多能釣魚的數(shù)量。

【輸入】

第一行一個整數(shù) n，表示湖的個數(shù)

第二行一個整數(shù) H，表示佳佳的空閑時間

第三行有 n 個整數(shù)，依次表示每個湖第一個 5 分鐘能釣到魚的數(shù)量

第四行有 n 個整數(shù)，依次表示以后的每5分鐘釣魚數(shù)量比前一個 5 分鐘釣魚數(shù)量減少的數(shù)量

第五行有 n?1 個整數(shù)，Ti 表示由第 i 個湖到第 i+1 個湖需要花 5×Ti分鐘的路程

【輸出】

輸出只有一行，表示佳佳最多能釣魚的數(shù)量。

【輸入樣例】

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; }

總結(jié)

以上是生活随笔為你收集整理的钓鱼（信息学奥赛一本通-T1431）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。