关灯问题 pascal

关灯问题：
在一条马路上，有一排灯，一个小朋友要去关灯，如果灯没有被关掉，就会每秒造成一定的损失。小朋友一开始在某一个位置，在他左边和右边分别有一些灯，给出这些灯和他的距离以及每个灯每秒会造成的损失，求一个方案使得损失最小，输出最小损失。灯的个数<=1000

没有样例啦...给个题解自己理解：
由于关掉的灯一定是一段连续的区间，所以，一个很基本的想法就是区间动态规划。下面要处理的，就是如何组织状态。
考虑一次关灯操作，从i走到j，花费了时间T，这时候，外面所有亮着的灯每秒总的损失是x，那么，这段时间的损失我们就定义为T*x。

我想要一个DP方程就可以了，有资料上说DP是O(N^2)的，我觉得是O(n^3)...求神牛给个方程，最好有解释...

f[i,j,k]表示左边关到i右边关到j，即i~j都关掉了,k表示状态，即你在左边还是右边k=0~1。那么这个状态可以转移到f[i-1,j,0],f[i,j+1,1],状态数2n^2，转移o(1)，总复杂度n^2
下面是一道类似的题目

在一个数轴上,有n个MM(绝非恐龙!)在哭泣(5555~一直哭).

tcboy也在这个数轴上,并恰好看到了这一幕,由于每个MM哭都会让tcboy损失一定的rp,于是tcboy有必要去安慰她们.(真命苦啊 T.T)

开始时，tcboy站在k号MM的旁边.

现在知道第i个MM哭泣每秒钟会使tcboy降低 w[i]的rp (单位rp/s).

而tcboy的行走速度很慢只有1m/s .

tcboy安慰MM的方式很特别(怎么安慰随便大家YY了..#@$%^%$#@),不需要花费时间.

请计算tcboy安慰完所有MM,会消耗掉的rp的最小值.

program cry;
var
f:array[0..1000,0..1000,1..2] of longint;
sum:array[0..1000,0..1000] of longint;
a:array[0..1000] of longint;
k,mi,ma,x,y,kk,s,n,i,j:longint;
function min(a,b:longint):longint;
begin
if a end;
function try(l,r,wz:longint):longint;
var
k:longint;
begin
if f[l,r,wz]<>0 then exit(f[l,r,wz]);
if (l>kk)or(r if (l=r) then begin
f[l,r,wz]:=0;
exit(f[l,r,wz]);
end;
f[l,r,wz]:=maxlongint;
if wz=1 then begin
k:=try(l+1,r,1)+s-sum[l+1,r];
if k k:=try(l+1,r,2)+(s-sum[l+1,r])*(r-l);
if k end;
if wz=2 then begin
k:=try(l,r-1,2)+s-sum[l,r-1];
if k k:=try(l,r-1,1)+(s-sum[l,r-1])*(r-l);
if k end;
exit(f[l,r,wz]);
end;
begin
readln(n,k);
mi:=maxlongint;ma:=0;
for i:=1 to n do begin
read(x,y);
if i=k then kk:=x;
if xma then ma:=x;
inc(s,y);
a[x]:=y;
end;
fillchar(sum,sizeof(sum),0);
fillchar(f,sizeof(f),0);
for i:=mi to ma do
begin
sum[i,i]:=a[i];
for j:=i+1 to ma do
sum[i,j]:=sum[i,j-1]+a[j];
end;
writeln(min(try(mi,ma,1),try(mi,ma,2)));
end.