題目描述#
話說發源於小朋友精心設計的遊戲被電腦組的童鞋們藐殺之後非常不爽，為了表示安慰和鼓勵，VIP999 決定請他吃一次「年年大豐收」，為了表示誠意，他還決定親自去釣魚。
但是，因為還要準備 NOIP2013，z 老師只給了他 H 個小時的空餘時間，假設有 n 個魚塘都在一條水平路邊，從左邊到右編號為 1, 2, 3 .. n 。
VIP 是個很講究效率的孩子，他希望用這些時間釣到盡量多的魚。他從湖 1 出發，向右走，有選擇的在一些湖邊停留一定的時間釣魚，最後在某一個湖邊結束釣魚。他測出從第 i 個湖到第 i+1 個湖需要走 5×Ti 分鐘路，還測出在第 i 個湖停留，第一個 5 分鐘可以釣到 Fi 條魚，以後每再釣 5 分鐘，可以釣到的魚量減少 Di ，若減少後的魚量小於 0，則減少後的魚量為 0 。為了簡化問題，他假定沒有其他人釣魚，也不會有其他因素影響他釣到期望數量的魚。請編程求出能釣最多魚的數量。
輸入輸出格式#
輸入格式：
第一行：湖的數量 n。
第二行：時間 h（小時）。
第三行：n 個數，f1，f2，… fn。
第四行：n 個數，d1，d2，….dn。
第五行：n-1 個數，t1，t2，….tn?1
輸出格式：
一個數，所能釣魚的最大數量。
輸入輸出樣例#
輸入樣例 #1：
2
1
10 1
2 5
2
輸出樣例 #1：
31
說明#
1 <= H <= 16
2 <= n <= 25
思路#
首先感謝 perisno 大佬
枚舉停止的池子，並計算出從頭走到這裡所需要的時間tm[i]（輸入時搞成前綴和）
則可釣魚的時間為(h-tm[i])
將前i個池子能釣的魚push進priority_queue裡，
在時間結束前pop出當前能釣最多魚的池子，
減去應減的數量再push回去。
這樣可以求出應在每個池子分別釣多久魚。
答案為在每個池子停留的最優解的最大值。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1e5+5;
struct pond{
int sl,jian;
friend bool operator <(pond a,pond b){
return a.sl<b.sl;
}
} a[MAXN];
int tm[MAXN];
int n,h;
priority_queue<pond> q;
int main(){
cin>>n>>h;
h*=12;
for(int i=1;i<=n;++i){
cin>>a[i].sl;
}
for(int i=1;i<=n;++i){
cin>>a[i].jian;
}
for(int i=1;i<n;++i){
cin>>tm[i+1];
tm[i+1]+=tm[i];
}
int ans=0;
for(int i=1;i<=n&&h-tm[i]>0;++i){
int cnt=0;
int ti=h-tm[i];
for(int j=1;j<=i;++j){
q.push(a[j]);
}
while(!q.empty()&&ti){
pond u=q.top();
q.pop();
cnt+=u.sl;
u.sl-=u.jian;
if(u.sl>0)q.push(u);
--ti;
}
ans=max(ans,cnt);
}
cout<<ans<<endl;
return 0;
}