动态规划。
去一个鱼塘必须经过前一个鱼塘，且走过就不能返回。假设在1-n这n个鱼塘钓鱼，可以预先减去从1到n需要的时间（反正迟早得走），然后无视“走过就不能返回”的限制，认为可以在鱼塘间自由切换（因为这样等价于在一个鱼塘钓够预定次数，再到下一个鱼塘）。
用堆维护和查找当前效率最大的鱼塘，并去那里钓鱼，之后更新堆……不断重复直到时间到。
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<queue> 8 using namespace std; 9 const int mxn=35; 10 struct fh{ 11 int f,d; 12 int id; 13 }a[mxn]; 14 15 bool operator < (const fh x,const fh y){ 16 if(x.f!=y.f)return x.f<y.f; 17 return x.id>y.id; 18 } 19 priority_queue<fh>q;//默认大根堆 20 int dis[mxn]; 21 int ans[mxn],tmp[mxn]; 22 int n; 23 void init(){ 24 memset(ans,0,sizeof ans); 25 memset(a,0,sizeof a); 26 dis[1]=0; 27 } 28 int main(){ 29 while(scanf("%d",&n) && n){ 30 init(); 31 int time; 32 scanf("%d",&time); 33 time*=12;//读入时间以小时为单位，实际计算时5分钟看做一个单位 34 int i,j; 35 for(i=1;i<=n;i++) a[i].id=i; 36 for(i=1;i<=n;i++) scanf("%d",&a[i].f); 37 for(i=1;i<=n;i++) scanf("%d",&a[i].d); 38 for(i=2;i<=n;i++){ 39 scanf("%d",&j); 40 dis[i]=j+dis[i-1]; 41 } 42 ans[0]=-1; 43 for(i=1;i<=n;i++){ 44 int mx=0; 45 memset(tmp,0,sizeof tmp); 46 int bas=time-dis[i];//可供钓鱼的时间 47 while(!q.empty())q.pop(); 48 for(j=1;j<=i;j++) q.push(a[j]); 49 fh x; 50 while(bas>0){//钓鱼 51 x=q.top(); 52 q.pop(); 53 bas--; 54 mx+=x.f; 55 tmp[x.id]++; 56 x.f-=x.d; 57 if(x.f<0)x.f=0; 58 q.push(x); 59 } 60 if(mx>ans[0]){//更新答案 61 ans[0]=mx; 62 for(j=1;j<=i;j++) ans[j]=tmp[j]; 63 } 64 } 65 for(i=1;i<n;i++)printf("%d, ",ans[i]*5); 66 printf("%d\n",ans[n]*5); 67 printf("Number of fish expected: %d\n\n",ans[0]); 68 } 69 return 0; 70 }