Ural 1029 ……

【引用】

所以，在同一层双向DP判断最小时，千万别加等号。DP完成后，可在最顶层搜索所有的代价最小的点，把到达这些点的路径统统扫描一遍，记录路径长度，选择长度最小的输出。

......就这句...

【/引用】

果然如此，要输出长度最小的。。这题的special judge有问题。

编译通过...

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

├ 测试数据 02：答案错误...程序输出比正确答案长

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

　├ 错误行输出

├ 测试数据 04：答案错误...程序输出比正确答案长

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

　├ 错误行输出

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

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

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

├ 测试数据 09：答案错误...程序输出比正确答案长

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

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

这题烦透了,才发现是可以让顶楼任意一个签证员签证,还不如规定称某一个呢,好麻烦的题啊,不想做了,回头问问2008Noip复赛考我们学校第一的zhangjuchuan大牛,借鉴一下程序……

竟然是双重 动归 ,动归和背包没学好~

所以，在同一层双向DP判断最小时，千万别加等号。DP完成后，可在最顶层搜索所有的代价最小的点，把到达这些点的路径统统扫描一遍，记录路径长度，选择长度最小的输出。

......就这句...

编译通过...

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

　├ 错误行输出

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

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

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

├ 测试数据 05：答案错误...程序输出比正确答案长

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

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

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

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

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

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

program qianzheng;

var m,i:0..101;

n,j,k,t:0..501;

w,f:array[0..101,0..501] of longint;

min:longint;

procedure out(i,j,m:longint);

begin

if i>0 then begin

if (f[m,j+1]

program xpbanzheng;

type

node=record

data:int64;

h:longint;

d:longint;

end;

const

maxn=500;

maxm=100;

var

a:array[1..maxm,1..maxn]of longint;

f:array[0..maxm,0..maxn] of node;

m,n:longint;

procedure print;

var

i,j:longint;

begin

writeln;

for i:=1 to m do

begin

for j:=1 to n do write('(',f.h,' ',f.d,')',' ');

writeln;

end;

end;

procedure Init;

var

i,j:longint;

begin

readln(m,n);

for i:=m downto 1 do

begin

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

f.data:=100000001;

readln;

end;

end;

procedure Main;

var

i,j,x,y,z,ans:longint;

begin

for i:=1 to n do

begin

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

f[1,i].h:=1;

f[1,i].d:=i;

end;

for i:=2 to m do

begin

for j:=1 to n do

if j=1 then

begin

f.data:=f.data+a;

f.h:=i-1;

f.d:=j;

end

else begin

if f.data

编译通过...

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

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

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

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

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

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

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

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

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

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

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

注意：

递归找路径时，定好边界不超。

核心：

dp每层两次。

最后，

加仔细！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

我很郁闷，我用了ANSI反而比STRING更快， 无语了……~~

双重动归，在生成当前状态时，注意从前到后，从后到前在动一次！

下面贴下主程序核心代码（仅供参考）：

for j:=1 to m do

begin

str (j,st);

zt[j]:=zt[j]+st+' ';

opt1:=opt1+map;

end;

for j:=2 to m do

if opt1>opt1+map then

begin

str (j,st);

zt[j]:=zt[j-1]+st+' ';

opt1:=opt1+map

end;

for j:=m-1 downto 1 do

if opt1>opt1+map then

begin

str (j,st);

zt[j]:=zt[j+1]+st+' ';

opt1:=opt1+map

end;

end;

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

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

Killed_After the 3rd Try

\

First:DP the UnderFloorRoom

Second:DP the RightRoom

Third:DP the LeftRoom

\

If not Then U'll Get 56 score Maybe...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

额，稀有的一次AC，上一次还是猩猩散步····遥远的历史啊

纪念一下。。。。。。。

大牛有题解，我就不贴了。。。

来说说大致方向

由于是要从第1层到第M层，并且每层都要选择费用最小的路径，所以应该分3次DP，分以下的阶段：

1、从第1层开始，到第M层：f[i][j] = f[i - 1][j] + a[i][j]

2、第i层从左到右：f[i][j] = min(f[i][j], f[i][j - 1] + a[i][j])

3、第i层从右到左：f[i][j] = min(f[i][j], f[i][j + 1] + a[i][j])

也就是传说中的双重DP。最后存储一下路径，输出即可。

注意，路径的存储是逆序的···我就在这上面磨了N久···

惨啊~~~

交了5次才AC。。。。

注意啊！78分的朋友注意了！

有两个点的数据只有一行啊~~~

路径注意只有第一行的输出啊~~~~~~

不错，一次AC，OTL。。。

每个签证员盖章都要收取一定费用，这个费用不超过1000000000。

签证员一定很富

编译通过...

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

├ 测试数据 02：内存溢出...

├ 测试数据 03：内存溢出...

├ 测试数据 04：内存溢出...

├ 测试数据 05：内存溢出...

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

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

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

├ 测试数据 09：内存溢出...

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

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

way:array[boolean(滚动数组),1..maxN,1..maxM*(maxN+2) div 2(可能最长路经——蛇形)]of longint;

内存会溢出……汗……如何是好……

不知道是longint的问题还是数组太大……

用spfa，并且耗费相同时路径要取最小

猥琐题...只是改了下推导方向就AC了...vijos判断不了多解..郁闷

-25 11:48:45 )

x50946702

郁闷ing

( 2008-10-22 12:54:55 )

---|---|---|---|---|---|---|-分割线---|---|---|---|---|---|---|---|---|---|---|---|

一年前看的题，今天终于AC了

编译通过...

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

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：89 有效耗时：82ms

郁闷，怎么会89分都打得出来

这是为什么呢？　我初值赋的就是极大值啊 fillchar(f,sizeof(f),$7f);

　　　　　　　　然后前驱赋的是0 fillchar(pre,sizeof(pre),0);

最后递归输出的边界 if (pre.s=0) and (pre.h=0) then exit;

编译通过...

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

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

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

├ 测试数据 04：运行超时|无输出...

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

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

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

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

├ 测试数据 09：答案错误...程序输出比正确答案长