byvoid魔獸世界模擬賽(編輯修改稿)
2025-08-11 17:53 本頁面
【文章內(nèi)容簡介】 放前面，坐標(biāo)大的放后面。 否則，如果 a與 b同為起點，則將優(yōu)先級大的放在前面，將優(yōu)先級小的放在后面，如果 a與 b同為終點，則將優(yōu)先級小的放在前面，優(yōu)先級大的放在后面。 否則，如果 a與 b一個為起點一個為終點，應(yīng)該把起點放在前面，終點放在后面。 這個算法的時間復(fù)雜度因維護(hù)優(yōu)先級集合的方法而異。 若用線性表維護(hù)，總時間復(fù)雜度為 O(n*n)；若用堆或排序二叉樹來維護(hù)，總的時間復(fù)雜度為 O(n*log n) 當(dāng)前掃描點： 優(yōu)先級集合： K的當(dāng)前值： K曾出現(xiàn)的值： (0,s,1) 1 1 1 (3,s,2) 2 2 2 (4,s,4)(5,t,1)(5,s,3) (6,t,3) (7,t,4)(8,t,2) 4 4 4 3 2ANS=3 分析此題，我們可以知道，從上游到下游，每過單位時間，船舶將向下游移動一個單位，而在移動的這個單位時，船舶可以選擇與河流流向垂直的方向移動一格或者不動。 目標(biāo)為在整個過程中，使經(jīng)過的格子的 寶藏 的數(shù)目之和盡量多。 艾薩拉的激流 很顯然，這是一個多階段決策的動態(tài)規(guī)劃問題。 設(shè)狀態(tài)為 f(i,j)示離上游距離為 i，距岸邊（指面向下游的左岸）距離為 j時，能夠吊上的最多的魚的數(shù)目。 狀態(tài)轉(zhuǎn)移方程： f(i,j)=max{f(i1,j),f(i1,j1),f(i1,j+1)｝ +fish(i,j)? 如果 (i,j)位置為障礙物，則 f(i,j)=－ INF。 初始狀態(tài) f(0,j)＝ 0 目標(biāo)狀態(tài) max{f(L,j)}(j=1..W)? 時間復(fù)雜度 O(W*L)? 這是一道比較簡單的動態(tài)規(guī)劃題目。 本題的變量比較多，有些麻煩。我們再來理清一下 船 、 聯(lián)盟 港口、結(jié)界的關(guān)系。 船 每天都有一個燃料的需求，而這個需求需
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號-1