题解 - Vijos

0

zgx LV 10 @ 2009-08-19 17:58:03

编译通过...

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

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

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

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

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

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

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

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

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

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

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

dp，类似于1006，可能还更简单。

0

20110422 LV 8 @ 2009-08-16 18:47:26

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

├ 测试数据 02：运行时错误...|错误号: -1073741571

├ 测试数据 03：运行时错误...|错误号: -1073741571

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

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

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

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

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

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

___|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\_|

错误号-1073741571 什么意思啊？

0

micro LV 8 @ 2009-08-07 01:24:43

＝。＝

2个答案过长，3个数据偏差。

44(分)×n(次)

0

wanly LV 8 @ 2009-08-04 21:46:18

……彻底无言了。。。

无聊切一下题。。。

就是DP。

最后输出的时候，因为没有spj（再次bs下vijos），所以要输出路径长度最短的。

0

fengyuchen LV 10 @ 2009-08-04 20:06:17

编译通过...

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

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

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

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

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

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

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

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

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

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

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

爽

0

xusc_2009 LV 9 @ 2009-08-04 13:33:43

35行……

贴代码不道德，所以不贴了……

数组不要开错，我wa这么多遍才发现……

0

how LV 10 @ 2009-08-01 17:56:44

3次才A的水题...

0

李肥888 LV 10 @ 2009-07-31 21:06:51

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

耶耶！！！

一次AC！！！！

爽！

爽爽！

爽爽爽！

爽爽爽爽！

爽爽爽爽爽！

爽爽爽爽爽爽！

爽爽爽爽爽爽爽！

===============晒程序===============

const d:array[1..3,1..2] of integer=((-1,0),(0,1),(0,-1));

var

i,j,n,m:integer;

f:array[0..100,0..501] of int64;

a:array[1..100,1..500] of longword;

ans:array[1..100,1..500] of integer;

procedure print(x,y:integer);

var

t:integer;

begin

t:=ans[x,y];

if x>1 then print(x+d[t,1],y+d[t,2]);

writeln(y);

end;

begin

readln(n,m);

for i:=1 to n do

for j:=1 to m do read(a);

for i:=1 to n do begin

for j:=1 to m do f:=f+a;

for j:=1 to m do ans:=1;

for j:=2 to m do begin

if f>f+a then begin

f:=f+a;

ans:=3;

end;

end;

for j:=m-1 downto 1 do begin

if f>f+a then begin

f:=f+a;

ans:=2;

end;

end;

end;

j:=1;

for i:=2 to m do

if f[n,i]

0

GD-becky LV 8 @ 2009-07-31 15:08:35

╮(╯▽╰)╭ 竟然会把(i,j-1)打成(i-1,j-1),看好久还没发现..

0

fs302 LV 8 @ 2009-10-30 21:39:29

哎，太相信题目了。被注释给误导了

注释 Hint

由于没有CHECK

请输出最短的路径

如果还是WA,请更换下更新解的条件,也许要加个等号

在判断的时候多给加了个等号，有2个点没过，好在vijos有数据给看。发现错误输出都比正确的小，看来不能有等号，把等号去掉就好了。看来以后还是得相信自己的判断。

for j:=1 to n do

f[1,j]:=a[1,j];

for i:=2 to m do

begin

for j:=1 to n do

begin

min:=maxlongint;

if (f1) and (f

0

qiusheng320 LV 8 @ 2009-07-27 15:57:44

郁闷，提交了14次终于Ac了。

就因为r[i][0].p=r[i][C+1].p=10000000000;和r[i][0].p=r[i][C].p=10000000000的不同。

#include

#define C 500

#define L 100

typedef struct {

int p;

int num;

int c;

}room;

room r[L+1][C+2];

int main()

{

int n,m;

int i,j,k,min,tmp[5000];

scanf("%d %d",&m,&n);

for(i=1;i

0

474182029 LV 8 @ 2009-07-25 20:07:37

一个比较大小的地方搞错了。。。我交了N次。。

0

340508965 LV 10 @ 2009-07-25 12:08:30

刚开始很兴奋有这么简单的题目然后很奇怪为什么只有16%通过率

但是不在意

然后看完题目看到输出格式的一句话"如果有多条费用最小的路线，输出任意一条。"

当时就在想：“天哪，vijos上怎么有这么先进的题目了?!!”

然后就很单纯地傻傻地写了最简单的交上去

结果...........( ⊙o⊙ )

编译通过...

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

├ 测试数据 02：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 03：运行时错误...| 错误号: 202 | 堆栈溢出错

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

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

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

Unaccepted 有效得分：67 有效耗时：0ms

后来 ........

看到

注释 Hint

由于没有CHECK

请输出最短的路径

如果还是WA,请更换下更新解的条件,也许要加个等号

诶最后不得不加了数组记录什么路径长度

~~~~(>_f+a then

begin

f:=f+a;

prex:=i; prey:=j-1;

l:=l+1;

end

else if f=f+a then

if l>l+1 then

begin

prex:=i; prey:=j-1;

l:=l+1;

end;

for j:=n-1 downto 1 do

if f>f+a then

begin

f:=f+a;

prex:=i; prey:=j+1;

l:=l+1;

end

else if f=f+a then

if l>l+1 then

begin

prex:=i; prey:=j+1;

l:=l+1;

end;

end;

min:=9999999999; y:=1;

for j:=1 to n do

begin

f[m,j]:=f[m-1,j]+a[m,j];

prex[m,j]:=m-1; prey[m,j]:=j;

l[m,j]:=l[m-1,j]+1;

if min>f[m,j] then

begin

min:=f[m,j];

y:=j;

end

else if min=f[m,j] then

if l[m,j]

0

yaoxin LV 8 @ 2009-07-23 17:58:36

编译通过...

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

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

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

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

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

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

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

var

i,j,m,n,k:longint;

a,f:array[1..100,1..500]of int64;

b,c:array[1..100,1..500]of longint;

t:array[0..50000]of longint;

procedure print(x,y:longint);

begin

if x=1 then writeln(y)

else

begin

if b[x,y]=1 then print(x-1,y)

else if b[x,y]=2 then print(x,y-1)

else print(x,y+1);

writeln(y)

end

end;

begin

readln(m,n);

for i:=1 to m do

begin

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

readln

end;

for i:=1 to n do

begin

f[1,i]:=a[1,i];

c[1,i]:=1

end;

for i:=2 to m do

begin

for j:=1 to n do

begin

f:=f+a;

c:=c+1;

b:=1;

end;

for j:=2 to n do if f+a

0

超子 LV 9 @ 2009-07-23 09:37:03

编译通过...

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

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

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

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

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

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

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

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

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

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

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

一定要细心……

0

lys_oson LV 8 @ 2009-07-16 11:33:58

我的AC率啊TT

在“=”时要更新路径的！！

真惊了，谁做的数据，拉出来打！！

0

guori12321 LV 8 @ 2009-07-15 11:34:01

总算AC了三次啊参考了楼下的程序，在此谢过

注意细节还是这句话我把m,n搞混了（正方形的真多，这个不是。。。），把j,k搞混的，但这样还是过了一多半的点改了40+min，写只写了30+min。一定要注意啊！！

总结一下，这道双DP（是这么叫吗）做一下还是有必要的首先要记录路径，其次要记录路径长度，还有，当f=f时有可能要更新路径和路径长度。

1.DP的初始化。DP就是初始化加递推，注意f[1,i]=a[1,i]

2.递归的输出路径。递归很好写啊，注意终止条件一定要有就行。

3.细节啊细节，大多数人就倒在这里了，我大部分时间就花在这里了。

做多了发现DP也不难.

还差3道就50了。努力！！！

0

hzhs_fxh LV 9 @ 2009-07-09 21:43:02

编译通过...

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

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

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

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

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

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

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

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

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

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

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

var

i,j,m,n,k:longint;

a,f:array[1..100,1..500]of int64;

b,c:array[1..100,1..500]of longint;

t:array[0..50000]of longint;

procedure print(x,y:longint);

begin

if x=1 then writeln(y)

else

begin

if b[x,y]=1 then print(x-1,y)

else if b[x,y]=2 then print(x,y-1)

else print(x,y+1);

writeln(y)

end

end;

begin

readln(m,n);

for i:=1 to m do

begin

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

readln

end;

for i:=1 to n do

begin

f[1,i]:=a[1,i];

c[1,i]:=1

end;

for i:=2 to m do

begin

for j:=1 to n do

begin

f:=f+a;

c:=c+1;

b:=1;

end;

for j:=2 to n do if f+a

0

src250 LV 10 @ 2009-06-23 11:29:37

VJ不支持special_judge！在循环的时候比如做dp的时候，要先循环j到1,再循环j到n,否则会WA！

0

tzk999 LV 7 @ 2009-05-17 14:22:06

编译通过...

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

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

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

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

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

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

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

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

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

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

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

{$N+}

var f,w:array[0..100,0..500] of extended;

i,j,k,n,m,x,y:longint;

ss,op:extended;

b:longint;

p:array[1..50000] of longint;

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

begin

if x>y then min:=y else min:=x;

end;

procedure kk(x,y,t:longint);

begin

if x1 then

begin

if f[x,y]=f[x-1,y]+w[x,y] then begin p[t]:=y;kk(x-1,y,t+1);end

else begin

if f[x,y]=f[x,y-1]+w[x,y] then begin p[t]:=y-1;kk(x,y-1,t+1);end

else begin p[t]:=y+1;kk(x,y+1,t+1);end;

end;

end;

end;

begin

op:=1000000001;

readln(n,m);

for i:=1 to n do for j:=1 to m do read(w);

for j:=1 to m do f[1,j]:=w[1,j];

for i:=2 to n do

begin

for j:=1 to m do

if j1 then f:=min(f,f)+w

else f:=f+w;

for j:=m-1 downto 1 do

begin

ss:=f+w;f:=min(f,ss);

end;

end;

for j:=1 to m do if op>f[n,j] then begin op:=f[n,j];x:=n;y:=j;end;

p[1]:=y;

kk(x,y,2);

b:=50000;

while p=0 do b:=b-1;

for i:=b downto 1 do writeln(p[i]);

end.

{靠，我三次才A，数据规模设小了，日}

题解

174 条题解

小胖办证

信息

状态

开发

支持

题解

174 条题解

小胖办证

信息

状态

开发

支持

还没有账户？

登录