枚举+贪心
把每钓5分钟鱼称为钓一次鱼。首先枚举John需要走过的池塘的数目X，即从池塘1走到池塘X。减去路上花去的时间T=sum(Ti) i=1...X-1，这样我们可以认为John能从一个池塘"瞬间转移"到另一个池塘，即在任意一个时刻都可以在池塘1到池塘X中任选一个钓一次鱼(很重要)。现在采用贪心策略，每次选择鱼最多的池塘钓一次鱼。对于每个池塘来说，由于在任何时候鱼的数目只和John在该池塘里钓鱼的次数有关，和钓鱼的总次数无关，所以这个策略是最优的。假设一共允许钓k次鱼，那么每次在N个池塘中选择鱼最多的一个钓。总的时间复杂度为O(kn^2)。 在最后的结果中，第一个最大值所对应的在每个池塘的钓鱼时间为题目要求的情况，因为如果John在后面的池塘钓了鱼，那么前面相应的时间就会减少。最后注意池塘中没有鱼的情况。
#include<iostream>
using namespace std;
int n,h,ans;
int f[26],t[26],d[26];
int main()
{
int i,k,total,j=0;
int fish[26],time[26],tt[26];
while(scanf("%d",&n)!=EOF&&n)
{
scanf("%d",&h);
h*=12;
for(i=1;i<=n;i++) scanf("%d",&f[i]);
for(i=1;i<=n;i++) scanf("%d",&d[i]);
t[1]=0;
for(i=2;i<=n;i++)
{
scanf("%d",&t[i]);
t[i]+=t[i-1];
}
ans=-1;
for(i=1;i<=n;i++)
{
total=0;
int remain=h-t[i];
memcpy(fish,f,sizeof(f));
memset(tt,0,sizeof(tt));
while(remain>0)
{
int maxn=-1,cur=-1;
for(k=1;k<=i;k++)
{
if(fish[k]>maxn)
{
maxn=fish[k];
cur=k;
}
}
total+=maxn;
fish[cur]-=d[cur];
if(fish[cur]<0) fish[cur]=0;
tt[cur]+=5;
remain--;
}
if(total>ans)
{
ans=total;
memcpy(time,tt,sizeof(tt));
}
}
if(j) printf("\n");
j=1;
for(i=1;i<=n;i++)
{
if(i==n) printf("%d \n",time[i]);
else printf("%d, ",time[i]);
}
printf("Number of fish expected: %d\n",ans);
}
return 0;
}
posted on 2010-08-10 20:13
wuxu 阅读(245)
评论(0) 编辑 收藏 引用 所属分类:
贪心