題目鏈接：poj ->http://poj.org/problem?id=1042

nyoj->http://acm.nyist.net/JudgeOnline/problem.php?pid=30

題意;有n個湖，每個湖都有fi條魚，每釣一次就會減少di條魚，

問一個人在給定的時間內(nèi)在按照從 1~n 湖中釣的魚最多是多少，

并輸出這個人在些湖中停留的時間

題解： 貪心 + 枚舉

注： 枚舉所有情況（即1~n的湖）每次找湖中魚最大的

#include<stdio.h> #include<string.h> int f1[30],f2[30]; int t[30],t1[30],t2[30]; int res[30]; int main() {int n,m,i,j,ret,q = 0;int time, time1 , time2;while(scanf("%d",&n),n){scanf("%d",&m);time = m * 60;memset(f2,0,sizeof(f2));for(i = 0 ; i < n; i ++){scanf("%d",&f1[i]);f2[i] = f1[i] ;}for(i = 0 ; i < n; i ++) scanf("%d",&res[i]);for(i = 1; i < n;i ++) scanf("%d",&t[i]);if(q) printf("\n");q = 1;int Max = -1;//這個max要小于0memset(t2,0,sizeof(t2));for(i = 0 ; i < n; i ++){memset(t1,0,sizeof(t1));for(j = 0; j < n ; j ++) f1[j] = f2[j];//還原time1 = time;for(j = 0 ; j <= i;j ++) time1 -= t[j] * 5;//去湖之間所用的時間time2 = time1;int sum = 0;while(time2 > 0){int max = 0；//注：這個max要等于0int flag = 0,p=0;for(j = 0 ; j <= i; j ++) //每次查找魚最多的湖{if(max < f1[j]){max = f1[j];p = j ;flag = 1;}}if(flag) t1[p] += 5;sum += max ;if(f1[p] > 0) f1[p] -= res[p] ;time2 -= 5;}if(Max < sum ){Max = sum ;ret = time1;for(j = 0 ; j < n ; j ++)t2[j] = t1[j] ;}}int ans = 0 ;for(i = 1; i < n;i ++) ans += t2[i];t2[0] = ret - ans ;printf("%d",t2[0]);for(i = 1; i < n;i ++)printf(", %d",t2[i]);printf("\n");printf("Number of fish expected: %d\n",Max);} }

總結(jié)

以上是生活随笔為你收集整理的poj-1042 nyoj-30（Gone fishing）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。