[計算機]新手的dota解題報告-資料下載頁
2025-03-23 02:14本頁面
【正文】 do for x3:=in+1 to n do for x4:=in+1 to n do for x5:=in+1 to n do begin f[i,x1,x2,x3,x4,x5]:=0。 for j:=1 to k do if f[i1,x1dx[j,1],x2dx[j,2],x3dx[j,3],x4dx[j,4],x5dx[j,5]]f[i,x1,x2,x3,x4,x5] thenf[i,x1,x2,x3,x4,x5]:=f[i1,x1dx[j,1],x2dx[j,2],x3dx[j,3],x4dx[j,4],x5dx[j,5]]。 pare(i,x1,x2,x3,x4,x5)。 end。 writeln(f[2*n1,n,n,n,n,n])。end.[數(shù)據(jù)目的]數(shù)據(jù)2：樣例；數(shù)據(jù)3~5：N小于等于6的數(shù)據(jù)。在這種情況下，可以采用非動態(tài)規(guī)劃形式求解：當(dāng)N小于等于5時，輸出所有單位的和；當(dāng)N等于6時，輸出所有單位的和減去對角線上最小的一格。數(shù)據(jù)6~10：N在7到10之間的數(shù)據(jù)。在這種情況下，應(yīng)使用動態(tài)規(guī)劃做法或搜索法，否則有可能得不到最優(yōu)解。尤其是N較大時，搜索法可能也會超時，應(yīng)選擇動態(tài)規(guī)劃來做。[心得體會]這道題的難度較低，只要從“方格取數(shù)”中借鑒一下即可。從“方格取數(shù)”這一經(jīng)典問題出發(fā)，我們還可以進行以下幾方面的修改：（1） 數(shù)字隨著取數(shù)的過程不斷變化或移動（按一定規(guī)律）；（2） 取數(shù)的進程更多（大于五甚至更多）；（3） 變二維至三維甚至多維，增加取數(shù)的范圍；（4） 設(shè)置障礙，不允許經(jīng)過此類方格（類似于“馬攔過河卒”）；（5） 起點和終點不定；（6） 方格內(nèi)數(shù)字有負(fù)數(shù)；（7） 取數(shù)方向考慮四個方向甚至多個方向。這些修改，可以只有一項，同時也可以疊加修改，對于修改過后的問題，題目類型也會隨之改變，算法將會有很大變化，由于動態(tài)規(guī)劃要滿足無后效性和最優(yōu)子結(jié)構(gòu)原則，所以修改過后的題目不一定適用動態(tài)規(guī)劃算法（如選擇修改中的（1）、（7）等），而可能轉(zhuǎn)而選擇搜索來求最優(yōu)解。對于這些題目，就有待進一步的研究了。針對“方格取數(shù)”，在網(wǎng)上流傳有使用網(wǎng)絡(luò)流解題的說法，但并沒有見到實現(xiàn)的程序，所以不敢多言。但可以看出，進行上述修改后，動態(tài)規(guī)劃已經(jīng)不能滿足解題需要了，而其他一些較為高級的求最優(yōu)解的方法可能正是解這類題的希望所在。2008年9月
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1