問題の説明#
ある日、子供たちが作ったゲームがコンピュータチームによって軽視されたことに非常に不満を感じた VIP999 は、慰めと励ましの意味を込めて、彼に一度「年年大豊作」をごちそうすることにしました。誠意を示すために、彼は自分で釣りに行くことにしました。
しかし、NOIP2013 の準備もしなければならないため、z 先生は彼に H 時間の余暇時間しか与えませんでした。水平な道路に沿って n 個の池があり、左から右に 1、2、3...n と番号がつけられています。
VIP は効率を重視する子供ですので、この時間を最大限に利用してできるだけ多くの魚を釣りたいと思っています。彼は湖 1 から出発し、右に向かって歩き、いくつかの湖で一定の時間を選んで魚を釣り、最後にある湖で釣りを終えます。彼は第 i の湖から第 i+1 の湖までの道のりが 5×Ti 分かかることを測定し、また第 i の湖で停止した場合、最初の 5 分で Fi 匹の魚を釣ることができ、その後の 5 分ごとに釣れる魚の数が Di 匹減少することを測定しました。減少後の魚の数が 0 より小さい場合、減少後の魚の数は 0 とします。問題を単純化するため、他の人が釣りをすることはなく、彼が望む数の魚を釣ることに影響を与える他の要素もありません。最大の魚を釣ることができる数を求めるプログラムを作成してください。
入出力形式#
入力形式：
1 行目：湖の数 n。
2 行目：時間 h（時間）。
3 行目：n 個の数、f1、f2、…fn。
4 行目：n 個の数、d1、d2、….dn。
5 行目：n-1 個の数、t1、t2、….tn?1
出力形式：
1 つの数、釣れる最大の魚の数。
入出力例#
入力例 #1：
2
1
10 1
2 5
2
出力例 #1：
31
考察#
1 <= H <= 16
2 <= n <= 25
解法#
まず、perisno さんに感謝します。
停止する池を列挙し、ここまでの時間tm[i]を計算します（入力時に累積和にします）。
釣りの時間は(h-tm[i])です。
最初のi個の池で釣れる魚をpriority_queueにpushします。
時間が終了するまで、最も多くの魚を釣ることができる池を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;
}