关灯问题 pascal
发布网友
发布时间：2024-10-23 03:28
共1个回答
热心网友
时间：2024-11-05 04:05
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<b then exit(a) else exit(b);
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<kk) then exit(maxlongint div 2);
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<f[l,r,wz] then f[l,r,wz]:=k;
k:=try(l+1,r,2)+(s-sum[l+1,r])*(r-l);
if k<f[l,r,wz] then f[l,r,wz]:=k;
end;
if wz=2 then begin
k:=try(l,r-1,2)+s-sum[l,r-1];
if k<f[l,r,wz] then f[l,r,wz]:=k;
k:=try(l,r-1,1)+(s-sum[l,r-1])*(r-l);
if k<f[l,r,wz] then f[l,r,wz]:=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 x<mi then mi:=x;if x>ma 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.
