信息學(xué)-集訓(xùn)隊作業(yè)_第1頁
免費預(yù)覽已結(jié)束，剩余2頁可下載查看

付費下載

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

FJ的N(2N1,000,000)頭奶牛選擇了接力跑作為她們的日常鍛煉項目。至于進(jìn)行接力跑的地點，自然是在牧場中現(xiàn)有的T(2<=T<=100)條跑道上。I1_i和I2_i(1<=I1_i<=1,000;1<=I2_i<=1,000)。每個交匯點都是至少兩條跑道的端點。奶牛們知道每條跑道的長度length_i(1<=length_i<=1,000)，以及每條跑道N頭奶牛在跑步開始之前都要站在某個交匯點上（1頭奶牛。當(dāng)然，她們的站位要保證她們能夠奶牛們跑步路徑可能的最小總長度。顯然，這條路徑必須恰好經(jīng)過N條跑道。程序名:relays輸入格式1行:4個用空格隔開的整數(shù)：N，T，S，以及2..T+1行:i+13個以空格隔開的整數(shù)：length_i，I1_iI2_i，描述了第i條跑道。輸入樣例2661144484662638輸出格式1行:1個正整數(shù)，表示起點為S、終點為E，并且恰好經(jīng)過N條跑道本題的交匯點的雖然非常大，但是題目中說明了交匯點都是至少兩條跑出一條從S開始經(jīng)過T條邊到達(dá)E的最短路。很容易想到用動態(tài)規(guī)劃方法求解：g[k,j]sjkg[k,j]=min{g[k-1,j’]+w[j’,j]}w[j’,j]j’j的路徑的權(quán)。這個算法的復(fù)雜度是OT2N。f[k,i,j]ijk個算法的復(fù)雜度是OT3N。這個狀態(tài)的優(yōu)勢是可以使用矩陣乘法進(jìn)行優(yōu)化。定義矩陣Ak[i][j]=f[k,i,j]，由狀態(tài)轉(zhuǎn)移方程可以知道，Ak是由Ak-1計算出來的，并且有Ak[i][j]=min{Ak-1[i][j’]+w[j’,j]}。通過觀察可以發(fā)現(xiàn)，它與可以定義一種矩陣運算法則BCA[ijmin{B[ikC[kj已知矩陣A的大小為ab，矩陣B的大小為bc，矩陣AB的大小為acABCi, cb Bk,lminminAi, l1k minminAi, c Bk,lminminAi,k

l

c minAi,k1

l

B AB

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論