我看还是DFS好做

var

n,m,i,min:longint;

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

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

function pan:boolean;

var

j:longint;

begin

for j:=1 to n do if f[j] then exit(false);

pan:=true;

end;

procedure dfs(i,l:longint);

var

j,x,k:longint;

begin

if l>=min then exit;

if pan then begin

min:=l;

exit;

end;

j:=i;

while not(f[j]) do inc(j);

if (j0) then begin

x:=0;

for k:=1 to n do if f[k] then x:=x+(a-a[j,1])*a[k,2];

f[j]:=false;

dfs(j,l+x);

f[j]:=true;

end;

end;

begin

read(n);

if n=0 then begin

writeln(0);

exit;

end;

read(m);

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

fillchar(f,sizeof(f),true);

f[m]:=false;

min:=maxlongint;

dfs(m,0);

writeln(min);

end.

f[i]表示第i盏灯有没有关，true表示开着，false表示关着。

min用来保存最优解。

搜索i左边第一盏没关的灯和右边第一盏没关的灯。

秒杀

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

dfs....AC50留念；

数据有点弱，记得优化，即得出一个结果min=(l=1,r=n) l指到最左边的点，r指到最右边的点

然后以后每次都判断 如果每步的结果>min就exit！否则数据变态的时候要2^49 个

dfs is strong

NND 耍我！！！！

谢谢 cheng199277 的提醒，秒杀

头很痛..随便做了.A了..

对应楼下的。。

纯的dfs

只要在搜索时把已经大于答案的剪掉。。

就0msAC。。。

30行的程序。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

数据弱，DFS也可以过，下面说一下我的DP方法

f[i][j]表示j开始从右向左走到i并关掉i的代价

g[i][j]表示i开始从左向右走到j并关掉j的代价

p[i][j]表示i--j间所有灯已关后每秒消耗的代价

简单的说，我们把灯划分为起始位置前与后两个部分

如果j在右边，关掉j灯，有2种大情况，

一：从j-1灯直接过来关掉j灯。

二：从j-1灯到前面部分的一个灯i，将其关掉，再回头将j关掉。

前半部分的转移同理

由此dp转移就出来了

f[i][j]==min(f[j]+(d-d[i])*p[j],g[j]+(d[j]-d[i])*p[j]);

g[i][j]==min(g[i][j-1]+(d[j]-d[j-1])*p[i][j-1],f[j]+(d[j]-d[i]*p[i][j-1]);

答案就是min(f[1][n],g[1][n])

楼下的DPS...

DPS+一个最优性剪枝！

剪枝为记录当前左边第一个开着的灯的点和右边第一个开灯的点和次时在哪个点，

如果下次搜索遇到比这个值大的时候就直接剪枝，效果非常明显。注意初始化把他们做成无限大。

简单的DFS以及一个最优剪枝就可以0ms了。。

一开始的时候做一个小小的预处理就OK

楼下有人说可以一开始就做好所有的费时，但是我是每做到一次都重新计算都是0ms。。

数据太弱了~

事实上。。。纯搜索。。枚举往左还是往右就可以了。。。

数据很弱的。。

编译通过...

要用long long

可以证明最多回头两次

就一个小小优化就可以过了

不加 50分

___|\__|_

|_^ v ^ _|

第一眼看到就下决心用 DP了。。。

由于只有50個燈。動歸記錄下位置，左邊關掉幾只右邊關掉幾只時的最小花費就行了。。

DP好像是行不通，转移方程不能包括所有的情况。

如果有大牛想出好的DP途径，请指点

刚才用DP才过了3个点，郁闷啊，哎！！！:-)

一个技巧

设数组left[i]为从1 到 i 的总功率

设数组right[i]为从i 到 n 的总功率

在搜索时只要将left[l]+right[r]加起来就得到往左走或右走的总功率了