【ybt1431】钓鱼
题目链接
【题目描述】
在一条水平路边，有 n 个钓鱼湖，从左到右编号为 1,2,…,n。佳佳有 H 个小时的空余时间，他希望利用这个时间钓到更多的鱼。他从 1 出发，向右走，有选择的在一些湖边停留一定的时间（是 5 分钟的倍数）钓鱼。最后在某一个湖边结束钓鱼。佳佳从第 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
【样例解释】
在第 1 个湖钓 15 分钟，共钓得 4+3+2=9 条鱼；
在第 2 个湖钓 10 分钟，共钓得 5+3=8 条鱼；
在第 3 个湖钓 20 分钟，共钓得 6+5+4+3=18 条鱼；
从第 1 个湖到第 2 个湖，从第 2 个湖到第 3个湖，共用时间 15 分钟，共得 35 条鱼，并且这是最多的数量。
【数据范围】
对于100%的数据，2<=n<=100,1<=H<=20
【题目分析】
由于只能向右走，可分别算出只在1-i(1<=i<=n)号湖中钓鱼的最大收益； 此时对于每次计算，在路上花费的时间是固定的，就可以减去这个时间，消除距离对答案的影响； 然后进行贪心：每次选择钓鱼数量最多的湖，统计数量，最后更新最大值。 用一个优先队列（大根堆）维护这些湖，每次取出的堆顶就是钓鱼数量最多的湖。 注意单位：H是小时数，以5分钟为一个单位，就在开头将H*=12; 每次将前i个湖放入堆中，每统计一次push一次 复杂度大概是O(n^2+hnlogn),对于n<=100可以接受
【参考程序】
#include<bits/stdc++.h>
#define go(i,a,b) for(register int i=(a);i<=(b);++i)
using namespace std;
const int maxn=30;
int n,h,ans,tot,t[maxn],d[maxn];
pair<int,int> a[maxn],s;
priority_queue< pair<int,int> > q;
int main() {
ios::sync_with_stdio(0),cin.tie(0); //关闭流同步，相当于读入优化
cin>>n>>h;h=h*12;
go(i,1,n) cin>>a[i].first,a[i].second=i; //读入数据，first是最初数量，second是减少数量
go(i,1,n) cin>>d[i];
go(i,1,n-1) cin>>t[i];
go(i,1,n) {
h-=t[i-1];tot=0; //计算剩余时间，由于向右枚举，所以时间是递减的，每次减少t[i-1]
while(!q.empty()) q.pop();
go(j,1,i) q.push(a[j]); //清空优先队列，并重新填充数据
for(register int j=h;j>0;--j) {
s=make_pair(q.top().first-d[q.top().second],q.top().second);
if(q.top().first>0) //注意：每次钓的鱼要为正数，否则就没有意义
tot+=q.top().first;
else break; //当前最多的湖也没有鱼了，就可以退出了
q.pop();q.push(s);
}
ans=(ans<tot?tot:ans); //更新答案
}
cout<<ans;
return 0;
}时间复杂度O(n^n)