[計算機]新手的dota解題報告-wenkub
2023-04-07 02:14:37 本頁面
【正文】 N以及所有兵力配置（只是開了一下全地圖可見……），五個英雄依次出發(fā)，每一次向右或向下移動一格，直到到達(dá)敵方的遠(yuǎn)古遺跡。在整張地圖上不僅有對方一撥撥的小兵，還有很多的野外中立兵。在經(jīng)過一番惡補之后，A君率先出師，隨后大家也紛紛學(xué)成。每個玩家僅需要選擇一個英雄，并通過控制該英雄來摧毀對方小隊所守護(hù)的主要建筑（遠(yuǎn)古遺跡），以取得最終勝利。作者聲明：當(dāng)動態(tài)規(guī)劃維數(shù)進(jìn)一步增大或不定時，標(biāo)準(zhǔn)解答方法為最大流。[題目描述]A君是暴雪公司的忠實FANS，也算是個war3的老手了，自從接觸到了DOTA之后，感覺這更適合自己這樣的微操狂人。接下來，就要進(jìn)行實戰(zhàn)演練拉。五個新手經(jīng)過討論，決定分別找出一條從自己老家（坐標(biāo)為1，1）通往敵方老家（坐標(biāo)為N，N）的路，一波RUSH直接結(jié)束戰(zhàn)斗。如果某個地點已經(jīng)被到達(dá)過，那么到達(dá)這一地點的英雄必然會殺死所有的處于該地點的單位，而且不再刷新。[輸入樣例1]31 2 32 3 43 4 5[輸出樣例1]27 //所有的單位都被解決了[輸入樣例2]62 5 6 7 9 16 4 8 6 8 41 6 9 8 4 81 6 8 4 1 69 8 7 4 6 38 4 1 0 3 1[輸出樣例2]181 //除了右上角的一個單位以外全部解決了[數(shù)據(jù)范圍]對于50%的數(shù)據(jù)，有0N≤6；對于100%的數(shù)據(jù)，有0N≤10；[命題目的]考察關(guān)于多進(jìn)程的高維動態(tài)規(guī)劃的知識與算法。由于要枚舉每一個點的坐標(biāo)，所以所需的空間復(fù)雜度達(dá)到O（n4），而時間復(fù)雜度也要達(dá)到O（n4）。我們考慮方格取數(shù)中可以使用的另一種方法。此后的每一步，X或Y的值中的一個加1，并且K加1，相當(dāng)于等式兩邊都加1，等式依舊成立。為了避免數(shù)組越界，同時方便計算，我們沿對角線將整張地圖分成兩部分：灰色部分的K值由1變化到N，相應(yīng)的各英雄坐標(biāo)的X值有可能是1~K中的任何一個。顯然，每一步英雄只有可能從其上方的格子或左邊的格子走過來。生成這個dx數(shù)組，可以用五重循環(huán)，或者用數(shù)組累加生成，復(fù)雜度都只是O（1）。我們將五個英雄的X值從小到大排序，用數(shù)組x記錄。[程序清單]program dota。 dx:array[1..32,1..5] of integer。 i,j,t:longint。x[4]:=x4。
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1