[計算機(jī)]dp-坐標(biāo)規(guī)則型動態(tài)規(guī)劃(編輯修改稿)
2024-11-15 03:41 本頁面
【文章內(nèi)容簡介】 j1,i2,j2)表示紙條 1到達(dá) (i1,j1)位置，紙條 2到達(dá) (i2,j2)位置的最優(yōu)值。則有， ? 其中 (i1,j1) (i2,j2) ? 1=i1, i2=M, 1=j1 , j2=N ? 時間復(fù)雜度 O(N2M2) ],[],[)1,1,()1,1(),1,1,(),1,1(m a x),( 221122112211221122112211 jiCjiCjijifjijifjijifjijifjijif ?????????????????????????分析 2 ? 另一種思路：每個紙條都需要走 M+N步才能達(dá)到目標(biāo)。 ? 因此，設(shè) F(k,i1,i2)表示兩個紙條都走了 K步，第 1個紙條橫坐標(biāo)為 i1,第 2個紙條橫坐標(biāo)為 i2的最優(yōu)值。 ? 則兩個紙條的縱坐標(biāo)分別為 j1=Ki1, j2=Ki2 ,狀態(tài)轉(zhuǎn)移方程如下： ? 其中 i1i2 ? 1=i1, i2=M,1=k=N+M ? 時間復(fù)雜度 O((N+M)*M2) ],[],[)1,1,1()1,1(),1,1(),1(m a x),( 22112121212121 ikiCikiCiikfiikfiikfiikfiikf ???????????????????????????免費(fèi)餡餅 ? SERKOI最新推出了一種叫做 “ 免費(fèi)餡餅 ” 的游戲。 ? 游戲在一個舞臺上進(jìn)行。舞臺的寬度為 W格，天幕的高度為 H格，游戲者占一格。開始時，游戲者站在舞臺的正中央，手里拿著一個托盤。 ? 游戲開始后，從舞臺天幕頂端的格子中不斷出現(xiàn)餡餅并垂直下落。游戲者左右移動去接餡餅。游戲者每秒可以向左或右移動一格或兩格，也可以站在愿地不動。 ? 餡餅有很多種，游戲者事先根據(jù)自己的口味，對各種餡餅依次打了分。同時在 8308電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格 /秒為單位。當(dāng)餡餅在某一秒末恰好到達(dá)游戲者所在的格子中，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1