poj 1042

题意：John有h个小时的时间想去钓鱼。（1<=h<=16）.有n个池塘(2<=n<=25)，它们的分布沿着一条单行的小路。John从第一个池塘处出发，他可以沿着小路向前走，在想停下来的池塘处钓鱼，对于路径的终点没有限制。为了钓到最多的鱼，John对各个池塘做了调查。若给路径上的池塘依次编号,，则对于每个池塘，开始钓鱼时，每5分钟内期望是可以钓到f[i]条鱼，随着时间的推移，每过5分钟，可以钓到的鱼减少d[i]条。若某个5分钟的时间段内可以钓到的鱼少于等于d[i]，则下一个5分钟在这个池塘就钓不到鱼了。用t[i]表示从池塘 i 到池塘 i+1 所需要的时间。单位是5分钟(==!), 即：若t[3] = 4,表示从池塘3到池塘4需要4*5=20分钟。John在每个池塘钓鱼的时间都必须是5的倍数。求期望能钓到最多鱼的钓鱼计划，并输出在每个池塘钓鱼的时间(分钟为单位)和能钓到的鱼总数。当有多个方案都是最优解时，选择在第一个湖的时间最长的方案，若仍相等，选择在第二个湖时间最长的方案，依此类推。

输出：第一行依次输出在每个池塘的停留时间(分钟为单位)，每个时间之间用逗号+空格分开。第二行输出能钓到的最多的鱼的数量。

思路：贪心+枚举，枚举到达哪一个池塘结束

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int n,m;
 5 int fi[30];  //鱼的数目
 6 int le[30];   //减少的数目
 7 int t[30];   //两个池塘的距离
 8 int ans[30];
 9 int temp[30];
10 int tempans[30];
11 
12 void update()
13 {
14     for(int i = 0; i<n; i++)
15         ans[i] = tempans[i];
16 }
17 
18 void solve()
19 {
20     memset(ans,0,sizeof(ans));
21     int road_time = 0;
22     int Max = -1,tmp = 0,time;
23     for(int i = 0; i<n; i++)
24     {
25         for(int j = 0; j<=i; j++)
26             temp[j] = fi[j];
27         memset(tempans,0,sizeof(tempans));
28         time = m - road_time;
29         tmp = 0;
30         while(1)
31         {
32             int most = -1,loc = -1;
33             if(time<5) break;
34             for(int j = 0; j<=i; j++)
35             {
36                 if(temp[j]>most)
37                 {
38                     most = temp[j];
39                     loc = j;
40                 }
41             }
42             if(most ==0)
43             {
44                 tempans[0]+=time/5*5;
45                 break;
46             }
47             tempans[loc]+=5;
48             tmp+=temp[loc];
49             temp[loc]-=le[loc];
50             if(temp[loc]<0)
51                 temp[loc] = 0;
52             time-=5;
53         }
54         if(tmp>Max)
55         {
56             Max = tmp;
57             update();
58         }
59         else if(tmp==Max)
60         {
61             for(int j = 0; j<n; j++)
62             {
63                 if(tempans[j]<ans[j])
64                     break;
65                 if(tempans[j]>ans[j])
66                     update();
67             }
68 
69         }
70         road_time +=t[i]*5;
71         if(road_time>m)
72             break;
73     }
74     printf("%d",ans[0]);
75     for(int i = 1; i<n; i++)
76         printf(", %d",ans[i]);
77     printf("
Number of fish expected: %d

",Max);
78 }
79 
80 
81 
82 int main()
83 {
84     while(scanf("%d",&n),n)
85     {
86         scanf("%d",&m);
87         m*=60;
88         for(int i = 0; i<n; i++)
89             scanf("%d",&fi[i]);
90         for(int i = 0; i<n; i++)
91             scanf("%d",&le[i]);
92         for(int i = 0; i<n-1; i++)
93             scanf("%d",&t[i]);
94         solve();
95     }
96     return 0;
97 }