經(jīng)典C題目目GoneFishing算法詳解及源代碼

1、.Gone Fishing算法詳解及源碼 這道題其實(shí)難在讀題上，因?yàn)檫@道題的細(xì)節(jié)太多，往往容易搞混，造成WA的情況，所以，學(xué)好英語還是有作用的。 解此題的主要方法是枚舉+貪心。剛開始的時(shí)候還沒想到一個(gè)好方法，因?yàn)楫?dāng)前魚最多的池塘是變化的，而題目所給描述里面的釣魚又是有順序的，即：John starts at lake 1, but he can finish at any lake he wants. He can only travel from one lake to the next one, but he does not have to stop at any lake unless

2、 he wishes to.所以，不可能在池塘中間瞬移，所以貪心貌似不能用。 但轉(zhuǎn)念一想，瞬移還是有可能的，當(dāng)確定了結(jié)束池塘ep（endpond）之后（結(jié)束池塘由1枚舉到n），我們便可以把從1到ep的交通費(fèi)用從h中減去，然后用剩下的時(shí)間貪心即可。因?yàn)樵诜治鰡栴}時(shí)，對(duì)于一個(gè)池塘，John在它上面什么時(shí)候釣魚并不重要，所以可以先把John看成很聰明的人，然后假設(shè)他已經(jīng)知道了在確定了結(jié)束池塘后，在每個(gè)池塘花多少時(shí)間使收益最大（實(shí)際上John是在貪心之后才知道的），這時(shí)我們就可以先減去交通費(fèi)用，然后在1ep的池塘中找現(xiàn)在的最大的即可。 這道題還比較容易WA，但最容易WA的地方還是全零的情況。法2，沒問

3、題：簡單題 直接枚舉結(jié)束湖泊+貪心選擇就可以了為什么可以貪心？（反正你要取的是最優(yōu)解 你可以假定自己知道最優(yōu)解 一路走過去的路上就直接取最優(yōu)解就可以了）因?yàn)榧?xùn)的時(shí)候這個(gè)題目莫名WA 故再A一遍 以解心頭之恨！using namespace std; 不能用time G+ CE多次 faintGone FishingSolution:/ by oyjpArt#include <iostream>#include <queue>using namespace std;const int N = 30;struct node int nf, idx; void set(in

4、t nn, int ii) nf = nn; idx = ii;int nl, time, fN, tN, dN, totf, stayN, beststayN;typedef priority_queue<node> PQ;bool operator<(const node&a, const node& b) if(a.nf = b.nf) return a.idx > b.idx; return a.nf < b.nf; int main () int i, j; while(scanf("%d", &nl), nl

5、) scanf("%d", &time); time *= 12; int maxf = -1; for(i = 0; i<nl; i+) scanf("%d", f+i); for(i = 0; i<nl; i+) scanf("%d", d+i); for(i = 0; i<nl-1; i+) scanf("%d", t+i); for(i = 0; i<nl; i+) memset(stay, 0, sizeof(stay); totf = 0; if(i>0) time

6、 -= ti-1; node now; PQ pq; for(j = 0; j<=i; j+) now.set(fj, j); pq.push(now); for(j = 0; j<time; j+) now = pq.top(); pq.pop(); staynow.idx += 5; totf += now.nf; now.nf -= dnow.idx; if(now.nf < 0) now.nf = 0; pq.push(now); if(totf > maxf) maxf = totf; memcpy(beststay, stay, sizeof(stay);

7、printf("%d", beststay0); for(i = 1; i<nl; i+) printf(", %d", beststayi); printf("nNumber of fish expected: %dnn", maxf); return 0;include<iostream>using namespace std;const int size=26;int n,h,ca;int fsize,tsize,dsize,tfsize;int anssize,tanssize,flag;int main()

8、 int i,j,k,sum,time,tt,tnum,maxsum,nextmin,t1;while(cin>>n) if(n=0)break;ca+; if(ca > 1) cout << endl; cin>>h;maxsum=-100;h*=60;t1=0; for(i=1;i<=n;i+) cin>>fi;tfi=fi; for(i=1;i<=n;i+) cin>>di; for(i=1;i< n;i+) cin>>ti; for(i=1;i<=n;i+) ansi=tansi=0;

9、 for(i=1;i<=n;i+) t1+=ti-1; time=(h-t1*5)/5;sum=0; for(j=1;j<=i;j+) tansj=0; if(i=1&&d1!=0) tans1=time; tt=f1/d1; if(f1%d1) tt+; if(time>=tt) sum=(f1+f1-(tt-1)*d1)*tt/2; else sum=(f1+f1-(time-1)*d1)*time/2; time=0; else if(i=1&&d1=0) tans1=time; sum=time*f1; time=0; while(ti

10、me>0) tnum=0;k=1;nextmin=0;flag=0; for(j=1;j<=i;j+) if(tnum<fj) tnum=fj; for(j=1;j<=i;j+) if(nextmin<fj&&fj!=tnum) nextmin=fj; for(j=1;j<i;j+) if(fj!=fj+1) flag=1;break; if(tnum=0) tans1+=time; break; if(flag=0|f1=tnum) sum+=f1; f1-=d1; if(f1<0)f1=0; tans1+; time-; conti

11、nue; for(j=1;j<=i;j+) if(fj=tnum&&dj!=0&&time>0) sum+=fj; tansj+; fj-=dj; time-;if(time<0)time=0; if(fj<0)fj=0; else if(fj=tnum&&dj=0&&time>0) tansj+=time; sum+=time*fj; time=0; break; if(maxsum<sum) maxsum=sum; for(j=1;j<=i;j+) ansj=tansj; for(j=

12、1;j<=n;j+) fj=tfj; for(i=1;i<=n;i+) cout<<ansi*5; if(i!=n) cout<<", " else cout<<endl; cout<<"Number of fish expected: "<<maxsum<<endl; return 0;問題描述：給定由n個(gè)整數(shù)（包含負(fù)整數(shù)）組成的序列a1,a2,.,an，求該序列子段和的最大值。當(dāng)所有整數(shù)均為負(fù)值時(shí)定義其最大子段和為0。依此定義，所求的最優(yōu)值為： 例如，當(dāng)(a1,a2,

13、 a3, a4, a5,a6)=(-2,11,-4,13,-5,-2)時(shí)，最大子段和為： 一個(gè)簡單算法：int MaxSum(int n, a, &besti, &bestj) int sum=0; for(i=1;i<=n;i+) for(j=1;j<=n;j+) int thissum=0; for(k=i;k<=j;k+) thissum+=ak; if(thissum>sum) sum=thissum; besti=i; bestj=j; return sum;算法有3重循環(huán)，復(fù)雜性為O(n3)。由于有：算法可作如下改進(jìn)：int MaxSum(int n, a, &besti, &bestj) int sum=0;for(i=1;i<=n;i+) int thissum=0;for(j=i;j<=n;j+)thissum+=aj;if(thissum>sum)sum=thissum;besti=i;bestj=j; 改進(jìn)后的算法復(fù)雜性為O(n2) 。從問題的解的結(jié)構(gòu)可以看出，它適合于用分治策略求解：如果將所給的序列a1:n分為長度相等的兩段a1:n/2和an/2+1:n，分別求