注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 1042 Gone Fishing 贪心+枚举  

2011-04-22 23:11:16|  分类: 贪心 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://poj.org/problem?id=1042
        John要以1到n的地点钓鱼,且只能从i点走到i+1点,从i点走到i+1点所花时间为5*ti。开始时每个地点的每五分钟之内可钓到鱼fi只,下一个五分钟会递减di。求在给定的时间内最多能钓到多少鱼。
        枚举钓鱼的结束地点。先总时间减去路上行走所花的时间。接下来我们可以想像为John可以在各个钓鱼地点之间瞬间移动,(从起点到结束点),那么在每个五分钟我们都可以选择钓到最多鱼的地点钓鱼。
       本题要注意,若有多个方案,要以在地点1花费时间多的为答案,若地点1的时间花费相同,则以地点2为基准,以此类推。
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> using namespace std; int f[30],d[30],t[30]; int n,h; int main() {   int i,j,num,flag,sum,ans[30],H,ff[30],ANS[30];     int max,fish,cas=1;       while(scanf("%d",&n),n)     {   memset(ANS,0,sizeof(ANS));   scanf("%d",&h);   for(i=0;i<n;i++)    scanf("%d",&f[i]);   for(i=0;i<n;i++)            scanf("%d",&d[i]);   for(i=0;i<n-1;i++)   {            scanf("%d",&t[i]);            t[i]*=5;   }           fish=-1;           h*=60;           for(i=0;i<n;i++)           {    H=h;    for(j=0;j<i;j++)     H-=t[j];    for(j=0;j<n;j++)     ff[j]=f[j];        memset(ans,0,sizeof(ans));        sum=0;    while(H>0)    {     max=-1;     flag=-1;     for(j=0;j<=i;j++)     {      if(ff[j]>max)      {       max=ff[j];       flag=j;      }     }     H-=5;     sum+=ff[flag];     ans[flag]+=5;     if(ff[flag]>d[flag])     ff[flag]-=d[flag];     else     ff[flag]=0;     //printf("%d.\n",sum);    }    if(sum>fish)    {     fish=sum;     for(j=0;j<n;j++)      ANS[j]=ans[j];    }    else if(sum==fish)    {     j=0;     while(ANS[j]==ans[j]&&j<=i)     j++;     if(j<=i)     if(ans[j]>ANS[j])     {      for(j=0;j<n;j++)       ANS[j]=ans[j];     }    }        }    if(cas!=1)   printf("\n");   cas++;   printf("%d",ANS[0]);   for(i=1;i<n;i++)   printf(", %d",ANS[i]);   printf("\n");   printf("Number of fish expected: %d\n",fish);  }  return 0; }    

  评论这张
 
阅读(173)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018