鏈接:https://vjudge.net/problem/POJ-1042
思路:貪心題。首先中途花費的時間總和只跟最終的終點有關(guān)耕拷,所以考慮枚舉終點。然后用一個優(yōu)先隊列儲存當前能釣魚的總量副瀑,每次取出最大的舱污,然后減去減少量再放入隊列想幻,注意如果存在相等的釣魚總量則取魚塘序號(靠前面)較小的哪一個粱栖,然后一直直到時間<5就結(jié)束。
代碼:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 30;
//魚塘脏毯,注意排序時如果相等就返回魚塘序號較小的那一個
struct fish{
int f,d,t,p;
bool operator<(const fish &a1)const{
if(f==a1.f) return p>a1.p;
return f<a1.f;
}
}ff[maxn];
int cc[maxn],dd[maxn];
int n,h;
int main(){
int o = 0;
while(scanf("%d",&n)&&n){
memset(dd,0,sizeof(dd));
scanf("%d",&h);
for(int i=0;i<n;++i)scanf("%d",&ff[i].f);
for(int i=0;i<n;++i)scanf("%d",&ff[i].d);
for(int i=0;i<n-1;i++)scanf("%d",&ff[i].t);
for(int i=0;i<n;i++)ff[i].p = i;
int res = 0;
for(int i=0;i<n;i++){
int times = h*60;
memset(cc,0,sizeof(cc));
priority_queue<fish> q1;
int ans = 0;
for(int j=0;j<i;j++)
times-=ff[j].t*5;//枚舉終點闹究,除去中間花費的時間
for(int j=0;j<=i;++j)
q1.push(ff[j]);
while(times>=5&&!q1.empty()){
fish z = q1.top();
q1.pop();
times-=5;
cc[z.p]++;
ans+=z.f;
z.f= z.f - z.d; //扣去每次釣魚后的魚塘總量減少量,再入隊
if(z.f<0)z.f=0;
q1.push(z);
}
if(ans>res){
res = ans;
for(int k=0;k<n;k++){
dd[k] = cc[k];
}
}
else if(ans==res){
int judge = 0;
for(int k=0;k<n;k++){
if(cc[k]>dd[k]){judge = 1;break;}
else if(cc[k]<dd[k])break;
else continue;
}
if(judge){
for(int k=0;k<n;k++){
dd[k] = cc[k];
}
}
}
}
if(o++)printf("\n");
for(int i=0;i<n-1;i++){
printf("%d, ",dd[i]*5);
}
printf("%d\n",dd[n-1]*5);
printf("Number of fish expected: %d\n",res);
}
return 0;
}