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