信息學(xué)國(guó)家集訓(xùn)隊(duì)作業(yè)power

1、ER題目大意：Dobrica 得到一份有趣的工作。每天早上他要將村莊里所有的路燈關(guān)閉，路燈都是安排在一條道路的一側(cè)的。Dobrica 每天 5 點(diǎn)開(kāi)始工作。一開(kāi)始，他站在某個(gè)路燈的旁邊。每個(gè)路燈有一個(gè)功率，也就是每秒鐘消耗的能量數(shù)。由于 Dobrica 是個(gè)很有經(jīng)濟(jì)頭腦的人，他希望所有路燈消耗的總能量最少。Dobrica 的速度是每秒鐘一米。關(guān)閉路燈不需要時(shí)間，因?yàn)樗梢栽诼愤^(guò)的時(shí)候隨手關(guān)掉。請(qǐng)你寫(xiě)一個(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(