无语，一个DFS+简单剪枝就可以秒杀，话说我有条类似的题数据量更加好

题目难度有待下方……

dp方法很经典..

虽然我用的dfs...

在一个全民搜索的时代里写DP真是很过意不去……不过我还是写了……

#define maxn 1001

#include

#include

#include

#define min(a,b) ((a)

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

WS水题……

l表示将i到j这段的灯关掉的最小功率且人在i处

r表示将i到j这段的灯关掉的最小功率且人在j处

然后很容易得到状态方程式……

两个剪枝

1.如果到最近的灯的距离加上当前功率，大于答案则减掉。

2.优先搜索功率大的一边(可以是当前的，也可以是剩余的)。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

用F表示 关掉点I到点J的灯并且最后在I上的MIN值

F表示 关掉点I到点J的灯并且最后在J上的MIN值

方程容易想，就是用F和F推下F;

提一下，预处理一个H表示关掉点I到点J的灯后还开的灯的总功率

var i,j,k,l,m,n,max:longint;

a,x:array[0..1000]of longint;

g:array[0..1000,0..1000]of longint;

f:array[0..1000,0..1000,0..1]of longint;

function min(x,y:longint):longint;

begin

if x

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

嫌dp方程麻烦的那就给我分行吧^_^

program power; var n,c,i,j:integer; a,d,s:array[1..1000]of integer; f:array[-1..1000,-1..1000,0..1]of longint; function min(a,b:longint):longint; begin if a

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

N^2的DP是王道= =

编译通过...

├ 测试数据 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

procedure dfs(p,q,x:integer;sp,sum:longint);

//p，q是到达的区间，x是当前所在的点，sp是当前总功率，sum是当前总花费

begin

if sum1 then dfs(p-1,q,p-1,sp-w[x],sum+(sp-w[x])*(a[x]-a[p-1])); //走左边 w是功率数组 a是坐标数组

if q

纠结的过了，最开始读入是时候第二个数以为是老张所在坐标....可惜，差点就一次AC了。DP方程绕过去绕过来的，差点被绕晕了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

要剪枝……

=======================puppy的分割线=======================

program v1150;

type rec=record

p,w:longint;

end;

var a:array[-1..51] of rec;

b:array[-1..51] of boolean;

i,n,c,x,y,l,h:longint;

min:qword;

procedure search(o,w,t,s:qword);

var wx,tx,temp:qword;

i,j,k:longint;

begin

if s=n

then begin

if w=min then exit;

end;

wx:=w; tx:=t;

if o1

then dec(j) else exit;

end;

b[a[j].p]:=true;

k:=abs(a[o].p-a[j].p);

inc(tx,k);

inc(wx,tx*a[j].w);

search(j,wx,tx,s+1);

wx:=w;

tx:=t;

b[a[j].p]:=false;

end;

end;

begin

readln(n,c);

l:=0; h:=maxint;

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

fillchar(b,sizeof(b),false);

b[a[c].p]:=true;

min:=10000000000000000000;

search(c,0,0,1);

writeln(min);

end.

此题第一组数据有问题，难道各位没发现？？！！！！！

第一组输入的是50，却有100行。而后面50行又没用！

所以请后面的人注意啊。。。。。。。。

我wa了n次!!!! 在“输出比标准答案长”后，终于AC。

输入

if (N == 50)

{

for (i = 1; i

楼下【lyrics】的dp题解听不懂……………

有没有神牛给具体解释一下

我的理解力不是一般差……

{数据弱，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]) }

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

若将n

DP？？我用的递归....，谁能讲讲

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

纯dp