首页 > 代码库 > 贪心/poj 1042 Gone Fishing
贪心/poj 1042 Gone Fishing
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 struct node 5 { 6 int d; 7 int fish; 8 int ans; 9 };10 node a[30],b[30];11 int t[30];12 int n,h,sum;13 int main()14 {15 scanf("%d",&n);16 while (n!=0)17 {18 memset(a,0,sizeof(a));19 memset(t,0,sizeof(t));20 scanf("%d",&h);21 h=h*12;22 for (int i=1;i<=n;i++) scanf("%d",&a[i].fish);23 for (int i=1;i<=n;i++) scanf("%d",&a[i].d);24 for (int i=1;i<n;i++)scanf("%d",&t[i]);25 sum=-1;26 for (int stop=1;stop<=n;stop++)27 {28 memset(b,0,sizeof(b));29 int time=h;30 int answer=0;31 for (int i=1;i<=stop;i++)32 {33 b[i].fish=a[i].fish;34 }35 for (int i=1;i<stop;i++) time-=t[i];36 37 for (int rest=time;rest>0;rest--)38 {39 40 int fishmax=1;41 for (int i=2;i<=stop;i++)42 if (b[fishmax].fish<b[i].fish) fishmax=i;43 44 answer+=b[fishmax].fish;45 b[fishmax].ans++;46 b[fishmax].fish-=a[fishmax].d;47 if (b[fishmax].fish<0) b[fishmax].fish=0;48 }49 if (answer>sum)50 {51 sum=answer;52 for (int i=1;i<=n;i++) a[i].ans=b[i].ans;53 }54 }55 for (int i=1;i<n;i++) printf("%d, ",a[i].ans*5);56 printf("%d\n",a[n].ans*5);57 printf("Number of fish expected: %d\n\n",sum);58 scanf("%d",&n);59 }60 return 0;61 }
贪心/poj 1042 Gone Fishing
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。