1042:Gone Fishing（贪心算法）

 1 转自大佬http://poj.org/showmessage?message_id=162286
 2 测试数据
 3 2
 4 1
 5 0 0
 6 1 1
 7 1
 8 答案
 9 60 0
10 0
11 
12 2
13 1
14 24 42
15 2 40
16 5
17 ans:
18 60, 0
19 Number of fish expected: 156
20 
21 3
22 1
23 10 10 10
24 10 10 10
25 11 0
26 
27 答案是
28 60，0，0
29 10
30 
31 3
32 1
33 0 76 50
34 0 30 7
35 20 13
36 
37 ans：
38 60, 0, 0
39 Number of fish expected: 0
40 
41 22
42 12
43 9 51 13 98 2 88 76 81 95 18 41 56 88 58 28 87 19 79 68 27 79 42
44 7 13 8 1 2 6 24 19 78 3 38 38 31 44 15 43 12 19 28 8 71 9
45 4 95 28 58 43 56 24 82 41 75 4 27 99 98 37 64 31 37 56 28 18
46 
47 Output:
48 0, 0, 0, 85, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
49 Number of fish expected: 1530
50 
51 25
52 1
53 0 27 81 78 66 2 67 70 95 56 73 83 30 52 3 31 99 55 83 94 65 32 99 57 97
54 0 2 81 24 14 2 49 65 23 11 68 0 17 20 3 4 1 45 2 18 52 21 87 6 35
55 26 68 63 58 98 32 94 67 57 13 38 7 25 92 50 56 27 48 30 42 34 98 51 6
56 
57 结果:
58 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
59 Number of fish expected: 0

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct Hu {
 5     int id,f,d;
 6 } hu[26];
 7 int n,h,tt,l[26],res[26],tmp[26],ans,now;
 8 bool operator < (const Hu &a,const Hu &b) {
 9     if(a.f==b.f)return a.id>b.id;
10     else return a.f<b.f;
11 }
12 priority_queue <Hu> q;
13 int main() {
14     while(cin>>n&&n!=0) {
15         cin>>h;
16         h=h*12;
17         ans=-1;
18         memset(res,0,sizeof(res));
19         for(int i=0; i<n; i++) {
20             cin>>hu[i].f;
21             hu[i].id=i;
22         }
23         for(int i=0; i<n; i++) {
24             cin>>hu[i].d;
25         }
26         l[0]=0;
27         for(int i=1; i<n; i++) {
28             cin>>l[i];
29             l[i]+=l[i-1];
30         }
31         for(int i=0; i<n; i++) {
32             now=0;
33             while(!q.empty())q.pop();
34             for(int j=0; j<=i; j++) {
35                 q.push(hu[j]);
36             }
37             memset(tmp,0,sizeof(tmp));
38             tt=h-l[i];
39             while(tt>0) {
40                 tt--;
41                 Hu p=q.top();
42                 q.pop();
43                 tmp[p.id]++;
44                 now+=p.f;
45                 p.f-=p.d;
46                 if(p.f<0) {
47                     p.f=0;
48                 }
49                 q.push(p);
50             }
51 
52             if(now>ans) {
53                 ans=now;
54                 for(int k=0; k<n; k++) {
55                     res[k]=tmp[k];
56                 }
57             }
58 
59         }
60         for(int i=0; i<n-1; i++) {
61             cout<<res[i]*5<<", ";
62         }
63         cout<<res[n-1]*5<<endl;
64         printf("Number of fish expected: %d \n",ans);
65 
66         if(n>0)cout<<endl;
67 
68     }
69 
70     return 0;
71 }