2122: 【J1】【动态规划】【优先队列】钓鱼
发布时间
阅读量：
阅读量
题目描述
约翰 钓鱼h小时（1≤h≤16，h*12个单位时间，5分钟为一个单位时间），
位于一条直线上的n个池塘共有2至25个。这些池塘依次编号为L₁, L₂, …, Lₙ。约翰花费tᵢ个单位时间从池塘Lᵢ前往池塘Lᵢ₊₁（其中i=1到n-1）。其出发点设于L₁位置。
约翰可以选择若干个池塘垂钓，并且在每个池塘他都可以选择任意数量的时间逗留。
随着钓鱼活动的持续进行,池塘中的鱼类数量逐渐减少.在第一个时间段内,池塘Li能够捕获的数量为Fi(其中 Fi 的取值范围为 0 到 100).随着时间的推移,在每一个后续的时间段内捕获的数量会依次减少一个固定的数值 di(其中 di 的取值范围同样是 0 到 100).为了帮助约翰实现这一目标,请设计一个算法来计算他能够捕获的最大数量鱼类的数量.
输入
输入文件第一行为一个整数n，
第二行为一个整数h，
第三行为n个用空格隔开的整数，表示Fi（i=1，2，…，n），
第四行为n个用空格隔开的整数，表示di（i=1，2，…，n），
第五行为n-1个用空格隔开的整数，表示ti（i=1，2，…，n-1）
输出
输出一个整数，表示约翰最多能钓到的鱼的数量。
样例输入
样例输出
Code:
#include<bits/stdc++.h>
using namespace std;
struct node{
int f,num;
bool operator<(node x)const{
return f<x.f;
}
}a[10005];
int n,h,d[10005],t[10005],ans;
priority_queue<node>q;
int main(){
cin>>n;
cin>>h;
h*=12;
for(int i=1;i<=n;i++){
cin>>a[i].f;
a[i].num=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++){
h-=t[i-1];
int now=0;
while(!q.empty()){
q.pop();
}
for(int j=1;j<=i;j++){
q.push(a[j]);
}
for(int j=1;j<=h;j++){
node s=q.top();
if(s.f>0){
now+=s.f;
}
s.f-=d[s.num];
q.pop();
q.push(s);
}
ans=max(ans,now);
}
cout<<ans;
return 0;
}全部评论 (0)
还没有任何评论哟~