信息學(xué)國(guó)家集訓(xùn)隊(duì)作業(yè)power_第1頁(yè)
信息學(xué)國(guó)家集訓(xùn)隊(duì)作業(yè)power_第2頁(yè)
信息學(xué)國(guó)家集訓(xùn)隊(duì)作業(yè)power_第3頁(yè)
全文預(yù)覽已結(jié)束

下載本文檔

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

文檔簡(jiǎn)介

1、ER題目大意:Dobrica 得到一份有趣的工作。每天早上他要將村莊里所有的路燈關(guān)閉,路燈都是安排在一條道路的一側(cè)的。Dobrica 每天 5 點(diǎn)開始工作。一開始,他站在某個(gè)路燈的旁邊。每個(gè)路燈有一個(gè)功率,也就是每秒鐘消耗的能量數(shù)。由于 Dobrica 是個(gè)很有經(jīng)濟(jì)頭腦的人,他希望所有路燈消耗的總能量最少。Dobrica 的速度是每秒鐘一米。關(guān)閉路燈不需要時(shí)間,因?yàn)樗梢栽诼愤^(guò)的時(shí)候隨手關(guān)掉。請(qǐng)你寫一個(gè)程序,幫助 Dobrica 安排一個(gè)關(guān)燈的路線,使得所有路燈所消耗的總的能量最少。輸入格式:文件的第一行是一個(gè)整數(shù) N(2=N=1000),表示路燈的數(shù)目。 第二行是一個(gè)整數(shù) V(1=V=N),

2、代表 Dobrica 初始時(shí)所在的路燈。接下來(lái)一共有 N 行,第 i+2 行有兩個(gè)整數(shù) D 和 W(0=D=1000,0=W=1000),表示第 i 個(gè)路燈距離路口的距離和它的功率。路燈根據(jù)離路口的距離按升序排列。輸出格式:一個(gè)整數(shù),表示最少消耗的總能量。保證這個(gè)數(shù)小于 1,000,000,000。解題思路:很經(jīng)典的一道動(dòng)態(tài)規(guī)劃的題目??紤]到對(duì)于任意一個(gè)時(shí)刻,關(guān)閉的路燈肯定是連續(xù)的(古人云,人已至此,不這樣定義狀態(tài):不關(guān))。Ri,j,1最少能量。Ri,j,2最少能量。 第 i 號(hào)到第 j 號(hào)路燈被關(guān)閉,且 Dobrica 在第 i 號(hào)路燈的情況下,消耗的 第 i 號(hào)到第 j 號(hào)路燈被關(guān)閉,且

3、Dobrica 在第 j 號(hào)路燈的情況下,消耗的有以下轉(zhuǎn)移方程式:Ri,j,1=MinRi+1,j,1+ (W1.i+Wj+1.N)*(Dj-Di) (W1.i+Wj+1.N)*(Di+1-Di),Ri+1,j,2+Ri,j,2=MinRi,j-1,1+(W1.i-1+Wj.N)*(Dj-Dj-1),Ri,j-1,2+(W1.i-1+Wj.N)*(Dj-Di) 整個(gè)算法的時(shí)間復(fù)雜度是 O(N2)。參考程序:progrower;constinfile=outfile=er.in;er.out;typearr=recordd,w:long; end;vard:array1.1000 of arr;

4、 r:array1.1000,1.1000,1.2 of long s:array0.1000 of long;n,st:eger;procedure readdata; varf:text;c1:eger; beginassign(f,infile);reset(f);read(f,n,st);for c1:=1 to n do read(f,dc1.d,dc1.w); close(f);s0:=0;for c1:=1 to n do sc1:=sc1-1+dc1.w; end;function min(o1,o2:long) : long; beginif o1o2 then min:=o

5、1 else min:=o2;end;procedure sub; varc1,c2,c3:eger; f:text;beginfor c1:=1 to n do for c2:=1 to n dofor c3:=1 to 2 do rc1,c2,c3:=1000000000;rst,st,1:=0; rst,st,2:=0; for c3:=2 to n do beginfor c1:=1 to n-c3+1 do begin c2:=c1+c3-1;rc1,c2,1:=min(rc1+1,c2,1+(sc1+sn-sc2)*(dc1+1.d-dc1.d),rc1+1,c2,2+(sc1+sn-sc2)*(dc2.d-dc1.d);rc1,c2,2:=min(rc1,c2-1,2+(sc1-1+sn-sc2-1)*(dc2.d-dc2-1.d),rc1,c2-1,1+(sc1-1+sn-sc2-1)*(dc2.d-dc1.d);end; end;assign(

溫馨提示

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

最新文檔

評(píng)論

0/150

提交評(píng)論