信息学国家集训队作业power

1、ER题目大意：Dobrica 得到一份有趣的工作。每天早上他要将村庄里所有的路灯关闭，路灯都是安排在一条道路的一侧的。Dobrica 每天 5 点开始工作。一开始，他站在某个路灯的旁边。每个路灯有一个功率，也就是每秒钟消耗的能量数。由于 Dobrica 是个很有经济头脑的人，他希望所有路灯消耗的总能量最少。Dobrica 的速度是每秒钟一米。关闭路灯不需要时间，因为它可以在路过的时候随手关掉。请你写一个程序，帮助 Dobrica 安排一个关灯的路线，使得所有路灯所消耗的总的能量最少。输入格式：文件的第一行是一个整数 N（2=N=1000），表示路灯的数目。 第二行是一个整数 V（1=V=N），

2、代表 Dobrica 初始时所在的路灯。接下来一共有 N 行，第 i+2 行有两个整数 D 和 W（0=D=1000，0=W=1000），表示第 i 个路灯距离路口的距离和它的功率。路灯根据离路口的距离按升序排列。输出格式：一个整数，表示最少消耗的总能量。保证这个数小于 1,000,000,000。解题思路：很经典的一道动态规划的题目。考虑到对于任意一个时刻，关闭的路灯肯定是连续的（古人云，人已至此，不这样定义状态：不关）。Ri,j,1最少能量。Ri,j,2最少能量。 第 i 号到第 j 号路灯被关闭，且 Dobrica 在第 i 号路灯的情况下，消耗的 第 i 号到第 j 号路灯被关闭，且

3、Dobrica 在第 j 号路灯的情况下，消耗的有以下转移方程式：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) 整个算法的时间复杂度是 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(