编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

type sh=record t,w:longint; end;var q:array [1..50] of sh; m,n,min,tot1:longint;procedure init;var i,j:longint;begin read(n,m); tot1:=0; for i:=1 to n do begin read(q[i].t,q[i].w); tot1:=tot1+q[i].w; end;end;procedure run(l,r,t,y,x:longint);var i:longint;begin if (l=1)and(r=n) then begin if x=min then exit; if y

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms ├ 测试数据 07：答案正确... 0ms ├ 测试数据 08：答案正确... 0ms ├ 测试数据 09：答案正确... 0ms ├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0m

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var

a,w:array[0..100] of longint;

v:array[0..100] of boolean;

i,j,n,m,min,t,tot,k:longint;

procedure dfs(x:longint);

var

i,j:longint;

begin

if tot>=min then exit;

if t=n then

begin

if tot

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

用递归写的深搜，加上两个剪枝，24行程序搞定。^_^

DFS ： 注意搜索的方向 + 一条最优化剪枝 = 秒杀

（当前位置想两边扩展） （now>ans->exit）

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

总算过了 刚开始一直90分 90分 90分...头都大了！！

program p1150;

var n,c,ans:longint;

x,p:array[0..50] of longint;

procedure init;

var i:longint;

begin

readln(n,c); ans:=99999999;

for i:=1 to n do readln(x[i],p[i]);

end;

function sum(l,k,r,t:longint):longint; //剪枝：从当前位置一直向左耗费+一直向右耗费

var i,j:longint;

begin

j:=0;

for i:=1 to l do j:=j+(t+x[k]-x[i])*p[i];

for i:=r to n do j:=j+(t+x[i]-x[k])*p[i];

sum:=j;

end;

procedure search(l,k,r,t,tot:longint); //左未关的灯，当前位置，右未关的灯，时间，功耗

begin

if tot>ans then exit; //有了这个剪枝我90分...

if (l=0)and(r=n+1) then

if ans>tot then begin ans:=tot; exit; end;

if (r0 then search(l-1,l,r,t+x[k]-x[l],tot+(t+x[k]-x[l])*p[l]); //向左走

if r

为什么LX的大牛说是两个小剪枝呢....我就一个小剪枝就AC了.....还是秒的...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

呵呵....我想我的代码还是比较容易读的....有初中英语水平就够了

var

n,i,j,min,t,f:longint;

position:array[1..50]of longint;

w:array[1..50]of longint;

b:array[0..51]of boolean;

function powersum(time:longint):longint;{}

var

i:longint;

begin

powersum:=0;

for i:=1 to n do

if b[i] then powersum:=powersum+w[i]*time;

end;

procedure dfs(p,r:longint);

var

i,j,m,a:longint;

begin

if t>min then exit; {传说中直接从50分到100分的剪枝？！}

if r=0 then

begin

if t0 then

begin

while not b[m] do dec(m);

if m>0 then{当然要保证路灯没被关掉，人也没走出范围啦～}

begin

a:=powersum(position[p]-position[m]);

t:=t+a;

b[m]:=false;

dfs(m,r-1);

b[m]:=true;

t:=t-a;

end;

end;

m:=p+1;{同上咯}

if m

很简单的DFS

只需记录当前开着的左边第一个和右边第一个

两个小剪枝

var

a,b:array[1..50] of integer;

n,m,i:integer;

he,min:longint;

procedure p(now,s,l:longint);

var i,k,g,ll:longint;

begin

if l>=min then exit;

if s>0 then

begin

for i:=now+1 to n do

if b[i]0 then begin

k:=b[i];

b[i]:=0;

g:=s-k;

ll:=l+abs(a[i]-a[now])*s;

p(i,g,ll);

b[i]:=k;

break;

end;

for i:=now-1 downto 1 do

if b[i]0 then begin

k:=b[i];

b[i]:=0;

g:=s-k;

ll:=l+abs(a[i]-a[now])*s;

p(i,g,ll);

b[i]:=k;

break;

end;

end else

if l

var

max,sum,s,t:longint; i,n,c:integer;

a,b:array[1..50] of longint;

d:array[0..51] of boolean;

function f(n:integer):boolean;

var i:integer;

begin

f:=true;

for i:=1 to n do

if d[i] then begin f:=false; exit; end;

end;

procedure find(k:integer);

var i,j,u:integer;

begin

if sum>=max then exit;

if f(n) then if sum

program vijos1150;

var n,c,i,j,ci,am,la:longint;w,pos:array[1..50] of longint;now,min,sum:longint;

l,r:array[1..50] of integer; flag:set of 0..51;

procedure try(i:integer;now:longint);

begin

if now>min then begin sum:=sum-w[i];exit;end;

if i>la then begin now:=now+sum*(pos[i]-pos[la]);l[i]:=l[la];end

else begin now:=now+sum*(pos[la]-pos[i]);r[i]:=r[la];end;

sum:=sum-w[i];

if am=n then begin

if now

var

a:array[0..51,1..2]of longint;

b,c,che,ch:array[0..51]of longint;

i,j,s,mins:longint;

m,n:integer;

function f:longint;

var

i:longint;

begin

f:=0;

for i:=1 to m do

if c[i]=0 then f:=f+a;

end;

procedure search(t,x:integer);

var

i,j,s1,s2:longint;

begin

if t>m then begin if s0)do

dec(i);

if i>0 then

begin

b[t]:=i;

s2:=abs(a[b[t],1]-a[b[t-1],1]);

s1:=f*s2;

c[i]:=1;

s:=s+s1;

search(t+1,i);

c[i]:=0;

s:=s-s1;

b[t]:=0;

end;

end;

begin

readln(m,n);

for i:=1 to m do

readln(a,a);

fillchar(c,sizeof(c),0);

s:=0;mins:=maxlongint;

b[0]:=n;

search(1,n);

writeln(mins);

end.

var

a,b:array [0..101] of longint;

turn:array [0..101] of boolean;

dit:array [0..101,0..101] of longint;

n,c,i,count,time,min,j,wei,abc:longint;

{procedure qsort(l,r:longint);

var

i,j,m,t:longint;

begin

i:=l;j:=r;

m:=a[random(r-l+1)+l];

while i1 then

try(wei,-1,1);

if wei

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DP!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

O(n2) DP

搜索写挂了，就写了一个O(n^5)的DP……

Program P1150;

Var i,j,k,l,m,n,min:longint;

a,b:array[0..51] of longint;

c:array[0..51] of boolean;

function find_left(input:longint):longint;

begin

find_left:=0;

for j:=input downto 1 do if c[j]=true then exit(j);

end;

function find_right(input:longint):longint;

begin

find_right:=0;

for j:=input to n do if c[j]=true then exit(j);

end;

function add(inset:longint):longint;

var i1:longint;

begin

add:=0;

for i1:=1 to n do if c[i1]=true then inc(add,b[i1]);

add:=add*inset;

end;

Procedure dg(time,loc,temp:longint);

var i2,place:longint;

begin

if time=n then

begin if temp0 then

begin

inc(temp,add(a[loc]-a[place]));

if temp>min then exit;

c[place]:=false;

dg(time+1,place,temp);

c[place]:=true;

dec(temp,add(a[loc]-a[place]))

end;

end

else

if i2=2 then

begin

place:=find_right(loc);

if place>0 then

begin

inc(temp,add(a[place]-a[loc]));

if temp>min then exit;

c[place]:=false;

dg(time+1,place,temp);

c[place]:=true;

dec(temp,add(a[place]-a[loc]));

end;

end;

end;

end;

end;

Begin

read(n,k);

for i:=1 to n do read(a[i],b[i]);

min:=1000000;

for i:=1 to n do c[i]:=True;

c[k]:=false;

dg(1,k,0);

writeln(min);

End.

Accepted 有效得分：100 有效耗时：0ms

dfs+剪枝=ms(秒杀)

楼上说得对，"因为关灯不需要时间，使之成为一道Water Problem！"

因为关灯不需要时间，使之成为一道Water Problem！

void dfs(int left,int right,int s,int loc)

//左边到了第几号,右边到了第几号,现在浪费了多少电,现在的位置编号(是left和right中一个,或许bool更合适)

{

if(rec[left][right][loc]>=s)

rec[left][right][loc]=s;

else

return;

...