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

1、.Gone Fishing算法詳解及源碼 這道題其實難在讀題上，因為這道題的細節(jié)太多，往往容易搞混，造成WA的情況，所以，學(xué)好英語還是有作用的。 解此題的主要方法是枚舉+貪心。剛開始的時候還沒想到一個好方法，因為當(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的交通費用從h中減去，然后用剩下的時間貪心即可。因為在分析問題時，對于一個池塘，John在它上面什么時候釣魚并不重要，所以可以先把John看成很聰明的人，然后假設(shè)他已經(jīng)知道了在確定了結(jié)束池塘后，在每個池塘花多少時間使收益最大（實際上John是在貪心之后才知道的），這時我們就可以先減去交通費用，然后在1ep的池塘中找現(xiàn)在的最大的即可。 這道題還比較容易WA，但最容易WA的地方還是全零的情況。法2，沒問

3、題：簡單題 直接枚舉結(jié)束湖泊+貪心選擇就可以了為什么可以貪心？（反正你要取的是最優(yōu)解 你可以假定自己知道最優(yōu)解 一路走過去的路上就直接取最優(yōu)解就可以了）因為集訓(xùn)的時候這個題目莫名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個整數(shù)（包含負整數(shù)）組成的序列a1,a2,.,an，求該序列子段和的最大值。當(dāng)所有整數(shù)均為負值時定義其最大子段和為0。依此定義，所求的最優(yōu)值為： 例如，當(dāng)(a1,a2,

13、 a3, a4, a5,a6)=(-2,11,-4,13,-5,-2)時，最大子段和為： 一個簡單算法：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)。由于有：算法可作如下改進：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; 改進后的算法復(fù)雜性為O(n2) 。從問題的解的結(jié)構(gòu)可以看出，它適合于用分治策略求解：如果將所給的序列a1:n分為長度相等的兩段a1:n/2和an/2+1:n，分別求