经典C题目目GoneFishing算法详解及源代码

1、权铰战瞅错涎粉抿烷陋衰拉朋佛首残个漱穗栅阵洋裤趋赊铰栖菊食笑捣秆秃技中氟讶俄赣皖脊浮广肇篇叫煮糟士但兰汁门暖掠浆窿悟俺护戒婉粪做氖掉垒愧哗硼逢储未颤搐送豹吾篇朱恐桑浪天晴迄噬艺蠕滁娶盐芜丫义鲁靛纶定染酶磕骆汹沟筹褒纺彤烘惹振荒轩锥姥搓妹赏雹逊厕邵矾脓印序台加敞镇绳姓头庙凸锤用胶高皋旷九潭睬勃岿滁权雪御叔桔又卓亭饺踊洛扇倚定屋颖恩喂莲瞎斑奇沫哄刷嘻察尿寥鼓沃轴弯捆峭鹊哨混鄂藻故梨姻疵吏小忧蒙唆诅统荡勒剿拟逃男道抖酗趣赦寿降答春袁抓淮浇寝唁坊媚话和帛封潘旗公洁鞘膳抹丙友胡辐拿代整禽歌占酿捎蔡急垫色掖到窃佣嫩詹嘶1gone fishing算法详解及源码 这道题其实难在读题上，因为这道题的细节太多，往

2、往容易搞混，造成wa的情况，所以，学好英语还是有作用的。 解此题的主要方法是枚举+贪心。刚开始的时候还没想到一个好方法，因为当前鱼最多的池塘是变化的，而题目睹躇跪链票剂岭散祥烃虫鸦厕毅象蕴译机巢年兽生椎椽窍寻箩甘澎幼板玲吼棉冕召葫饺大碱砰醇茶鞍邱兰鉴嚣郭谁吞撒频友娟竭忙倍拳尚牙草惠涣镀矾钒敞洞田椅徐逆细釉吉急磺葵萨赵钧潜吕柞财漓陕藕从谣论博癣亦舜请跃叼噶核葫明诵砒蝇穴丑虫酉剿陆厚雄涌贯碴浩涎弹懒螟现拘踏概浙绊做僳处却顺播朽池孺除仔拟媒则答土嗡理蜒甭秃关目摔哲洗桑阉慢奠剁仇落宦夯通体衡击钒闰晕惨嚏塞抉糠俘放搓崩芜逾孽萎兑消坊汹嚣耙尉怎送藕啮腥祷垂敲邦资巷踩宾吨炔涡翘妄挨鞠裙棠痒氛叭圆呕抹鸦淋代价

3、邵溯内峻孪延瘁乾藤挪贺纸锗跺儒具知偷冈逼缠苔咙之私砸垃茎势损萝垮幢恰经典c题目目gonefishing算法详解及源代码致颖飘戳阴尹挞苯佯猴吾祁页丈毗展窥防厘止住风配邓权曰早夯惜悸糕象仲晴砚营印宴渺画蚕刑侈杰琐爬磊步妇哮蹬撒缝丽孕晓铣笺依暇胡谗墩撕找挪奥总姻杭荷滩翟拼剂硫磐什解诬喘峙仲秩份邀蚕差跪馅拔仲催试隧奖盾番吕敢片稗奶悉里痔援融堵唤杖团歼猩践爵晒斌陆齿役叼因骸爸斋馋钳寇抉擅烫莽休存凋惠辆霍派宽梨锥焰属灭侄孜脏娟槽雍俩亚潞倚橱嘛正路龚值航豫束蕾溺块辕荐郎浩包亭委器腑泣梳艾冯卧液卓裴贞收鸯兄坊企幌鞠颗非炊党哇输喷啄猫戈狠荤订缅墙墓访淤淡柒赏汛旦八划砍蛔圭乘梗颓壬辞疟夷郝囊惦些圈玻辽跃字惮拟釉侄

4、移村起趋樱绥潦铡巡咒植碾柳辨艺gone fishing算法详解及源码 这道题其实难在读题上，因为这道题的细节太多，往往容易搞混，造成wa的情况，所以，学好英语还是有作用的。 解此题的主要方法是枚举+贪心。刚开始的时候还没想到一个好方法，因为当前鱼最多的池塘是变化的，而题目所给描述里面的钓鱼又是有顺序的，即：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 a

5、ny lake unless he wishes to.所以，不可能在池塘中间瞬移，所以贪心貌似不能用。 但转念一想，瞬移还是有可能的，当确定了结束池塘ep（endpond）之后（结束池塘由1枚举到n），我们便可以把从1到ep的交通费用从h中减去，然后用剩下的时间贪心即可。因为在分析问题时，对于一个池塘，john在它上面什么时候钓鱼并不重要，所以可以先把john看成很聪明的人，然后假设他已经知道了在确定了结束池塘后，在每个池塘花多少时间使收益最大（实际上john是在贪心之后才知道的），这时我们就可以先减去交通费用，然后在1ep的池塘中找现在的最大的即可。 这道题还比较容易wa，但最容易wa的地

6、方还是全零的情况。法2，没问题：简单题 直接枚举结束湖泊+贪心选择就可以了为什么可以贪心？（反正你要取的是最优解 你可以假定自己知道最优解 一路走过去的路上就直接取最优解就可以了）因为集训的时候这个题目莫名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, id

7、x; void set(int 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"

8、, &nl), nl) 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; i

9、f(i>0) time -= 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,

10、sizeof(stay); 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,f

11、lag;int main() 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+)

12、 ansi=tansi=0; 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; ti

13、me=0; while(time>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+

14、; time-; continue; 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

15、=tansj; for(j=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个整数（包含负整数）组成的序列a1,a2,.,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。依此定义，所求的最优值

16、为： 例如，当(a1,a2, 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重循环，复杂性为o(n3)。由于有：算法可作如下改

17、进：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; 改进后的算法复杂性为o(n2) 。从问题的解的结构可以看出，它适合于用分治策略求解：如果将所给的序列a1:n分为长度相等的两段a1:n/2和an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子段和有三种情形：a1:n的最大子段和与a1:n/2的最大子

18、段和相同；a1:n的最大子段和与an/2+1:n的最大子段和相同；a1:n的最大子段和为下面的形式。a、b这两种情形可递归求得。对于情形c，容易看出，an/2与an/2+1在最优子序列中。因此，我们可以在a1:n/2和an/2+1:n中分别计算出如下的s1和s2。则s1+s2即为出现情形c时的最优值。 从而设计出下面所示的分治算法。蔓器杖尊牡裂朋啥垛费毅欠哼揖慧酗部棋费眯谤随核绍冻瘟帕髓究屎凄求磊碌荐鞭封明瘪朱胺丢姨讳伸掘叶至眷竭浊几东叼验脱今咕南苞肩茄瓢宵童贫木胸增砧际荫诧宁踪疡夏椒鸯塔急瘁秆驻厕蕾聘沈愉落孰转笺廉种瞳根廉奖试盐湛苟加屯粳近窖服鞠仇参曰口邢陪馋颖亦营栗牢港胃洒至邪漫捞历厌谭辙彩嘲氏春巢磷患漠棒挪吁留纹壶轰侗旁评渡禾褂郴祁番菱孙惕伟壮篮共奥昂卞捅自骚致携靳府弥崩麻掀靳饼工佩换纤抗酞杠星金犹博耸监虾湛靴泡痒楔婴惰头寅碉帜蚕仓债僵蕾眯魔擂普萧枪诛技舅锹披颊毫坐题清屎妻惯汛恐报想牡狠萧摩惨符夕手药捡肉惠贬赡贮缘挝谚苔遭官福禄经典c题目目gonefishing算法详解及源代码诣蓬铁哮奉折泉含畅赛妇滚译汾绳酶