题解 - Vijos

0

LV 0 @ 2009-08-25 20:38:39

膜拜oimaster的点击此处

0

sto LV 9 @ 2009-08-25 00:56:24

个人感觉此题的标号比较有特点

首先把发电站标上0号，四周标上1..4号，然后从已标号的点中选一个点使该点的标号比上一个扩展的点的标号大，将此点扩展，同时把此点周围的点标号。

有了标号之后，再按照标号搜索。这样保证了状态的“不重不漏”

除此之外，为了提高效率，还要再加一个最优化剪枝。即当前已获得的价值+矩阵内最大价值*剩余区域数

-1

Ey3JeU LV 10 @ 2017-09-02 14:04:47

7年之后

-1

ayzk LV 7 @ 2009-11-06 21:16:04

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

可惜了，最后一组.

标号搜索+可行性剪枝+范围限制=AC

//PROGRAM power

//MADE BY AYZK

//DATE 2009-11-03

const

dx:array[1..4] of integer=(0,0,-1,1);

dy:array[1..4] of integer=(-1,1,0,0);

var

v:array[0..501,0..501] of integer;

visit:array[0..501,0..501] of boolean;

labe:array[0..501,0..501] of longint;

val:array[0..1000] of longint;

canuse:array[0..21] of integer;

n,m,t,i,j,maxcost,k,l1,l2,r1,r2:integer;

number,tlabe:longint;

procedure dfs(l1,l2,r1,r2:integer;lab,step,cost:integer);

var

relab:array[1..4] of boolean;

i,j,k,x1,y1,i1,j1,l3,l4,r3,r4:integer;

begin

if step=t+1 then

begin

if cost>maxcost then

begin

maxcost:=cost;

number:=1;

end else

if (cost=maxcost) then number:=number+1;

exit;

end;

if cost+canuse[t-step+1]lab)and(not visit) then

begin

l3:=l1;

l4:=l2;

r3:=r1;

r4:=r2;

visit:=true;

fillchar(relab,sizeof(relab),0);

for k:=1 to 4 do

begin

x1:=i+dx[k];

y1:=j+dy[k];

if (x1>n) or (x1m) or (y1t then exit;

canuse[t1]:=canuse[t1-1]+i;

end;

end;

begin

assign(input,'power.in');

reset(input);

assign(output,'power.out');

rewrite(output);

fillchar(visit,sizeof(visit),0);

readln(n,m,t);

for i:=1 to n do

for j:=1 to m do

begin

read(v);

if v=1000 then

begin

l1:=i-1;

l2:=i+1;

r1:=j-1;

r2:=j+1;

if l1=0 then l1:=1;

if r1=0 then r1:=1;

if l2>n then l2:=n;

if r2>m then r2:=m;

visit:=true;

for k:=1 to 4 do

if (i+dx[k]>0)and(i+dx[k]0)and(j+dy[k]

-1

zhfgogogo LV 10 @ 2009-11-06 17:14:32

编译通过...

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

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

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

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

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

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

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

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

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

├ 测试数据 10：运行超时...

编译通过...

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

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

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

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

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

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

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

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

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

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

同样的程序.....

-1

voyagec2 LV 10 @ 2009-10-02 20:37:27

这种题难怪没人做

-1

oimaster LV 10 @ 2009-09-20 18:27:37

一看到搜索题我就委掉了……

-1

hhdllhflower LV 10 @ 2009-08-31 23:01:13

楼下的好强~

Orz Orz Orz~

-1

怪盗~基德 LV 10 @ 2009-08-31 22:59:57

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Yes，秒杀！！！！！！

-1

Hyd_1992 LV 9 @ 2009-08-26 17:42:52

好一道囧搜题……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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