集訓(xùn)隊作業(yè)-會飛小豬解題報告

【正文

一、問題描述某一列的小豬朝向同一個方向。tiin出ti二 問題分析優(yōu)解?？梢栽O(shè)計出一些貪心策略解決這題。算法一 優(yōu)化一：不一定要等第i只豬到達了豬圈后才去處理第i+1只豬。只需它就能夠到達豬圈。當(dāng)然吹后面的豬的時候，不能影響前面的豬的方向。這樣就節(jié)省了很多無謂的等待時間。優(yōu)化二：把隨便找一只豬改成挑一只離豬圈距離Si中最小的豬。這樣算法二引入一個量：狀態(tài)的值。對于每個狀態(tài) 值來評價狀態(tài)的好壞。在這題中計算狀態(tài)的值的方法為：狀態(tài)的值nSi。其中Si表示第i只豬離它最近的豬圈的距離 優(yōu)化：M值越小，并不一定說明狀態(tài)越好。因為有可能兩只豬i,j。Si,Sj取到kM值并不能準(zhǔn)確反引入隨機化，每次不一定取最小的M值，因為有時候取到第k小的M值反算法三k:←Random(Rate)ifk>0thenMin←M

不同的數(shù)據(jù)，取到最優(yōu)解的時候，MaxnRate1∞23552∞373∞64226∞77∞385922∞5【附錄1、ProgramConstMaxn=1000;h:array[1..4,1..2]ofTypea:array[1..Maxn2,1..Maxn2]ofShortint;Value:array[1..Maxn2,1..Maxn2]ofLongint;d:array[1..2,1..Maxn2]ofLongint;g:array[1..9,1..2]ofLongint;Blow:array[1..8,1..Maxn2]ofLongint;Point,Step:array[1..Maxn1]ofLion;Pig,Pig_bak:array[1..Maxn1]ofLion1;RestTime:array[1..Maxn1]ofLongint;ProcedureVari,k,Min:longint;fori:=1tomdoforj:=1to9doifk<MinthenVari,j:Longint;fori:=1tomdoif(Point[i].x=x)and(Point[i].y=y)thenforj:=itom-1doProcedureMove(Varx,y,bj:Longint);Casebjofifx>nthenelseifx<1thenx:=n;ify>ntheny:=1elseify<1theny:=n;ProcedureMovePigs(VarNow1,Now2:longint;bj1,bj2:longint);Vari,j,Now1_bak,Now2_bak:longint;fori:=1tototdoifa[Pig[i].x,Pig[i].y]=1thenifi<=Now1_bakthendec(Now1);ifi<=Now2_bakthendec(Now2);forj:=tot1+1totot-1doend;End;fori:=1tototProcedureVarifValue[x,y]<0thenValue[x,y]:=Cal(x,y);WhileTime<Maxnfori:=1tototdofori:=1ton fori:=1tondoforj:=1to4doifk<MinthenifRan>0thenfori:=1tototif(((bj1=4)or(bj1=6))and(bj2=Pig[i].x))thenPig[i].Dir:=bj1;iftot=0thenbreak;fori:=1tomdoProcedureVari,j,Start,k,Now,x,y,yy, Whilei<totdoWhilebbdoforj:=StarttototdoifDis<MinthenifMin=Maxlongintthenbak:=Pig[Start];Pig[Start]:=Pig[k];Pig[k]:=bak;bak:=Pig[Start];Pig[Start]:=Pig[i];Pig[i]:=bak;ify>ymthen elseify<ymthen ifx>xmthenSecond:=8elseifx<xmthenSecond:=2elseSecond:=0;if( <>Pig[i].Dir)thenforj:=1toi-1doifRestTime[j]>0if(Pig[j].x=Pig[i].x)and(Pig[j].Dir<> )thenif(Can)and(Second<>0)and(Second<>Pig[i].Dir)thenforj:=1toi-1doifRestTime[j]>tthenCasePig[j].Dirofifyy<1thenyy:=yy+n;ifyy>nthenyy:=yy-if(yy=ym)and(Pig[j].Dir<>Second)thenifCanthen <>0then <>Pig[i].Dirthenforj:=1tototifPig[j].x=Pig[i].xthen elseifSecond<>0thenif(Second<>0)and(Second<>Pig[i].Dir)thenforj:=1totdoMovePigs(i,k,5,0);forj:=1tototdoifPig[j].y=Pig[i].ythenPig[j].Dir:=Second;ifbbthenWhiletot>0doMovePigs(i,k,5,0);ProcedurePrint;Vari:Longint; fori:=1toTimedoCaseStep[i].xofifStep[i].x=5then