我太激动了！！！！

终于AC了！

此题太ws了！

一定要注意dp要这样的顺序：

3 4

10 10 1 10 ……1

2 2 2 10 ……2

1 10 10 10 ……3

要以3-2-1的顺序dp

此时输出要先记路径再逆序输出。

就像楼上的牛说的，搜2次

第一次是局部的最优解，第2次得到当前的真正的最优解。。。

之后我用了一个三维数组记录每个点的前驱

搜索完了后找到最后一行的最小值，从它开始把前驱一个一个得输出去就是了

最后，附个证书和核心程序。。。MS这里还没有程序的说。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

for i:= 1 to n do begin f[1,i]:=a[1,i]; if a[1,i] < min then begin min:=a[1,i]; flag:=i; end; end;

if m = 1 then writeln(flag)

else begin

for i:= 2 to m do

begin

for j:= 1 to n do

if j = 1 then begin f:=f+a; re:=j; end

else begin

f:=f+a; re:=j;

if f > a+f then begin f:=a+f; re:=j; end;

if f > a+f then begin f:=a+f; re:=j-1; end;

end;

for j:= n downto 1 do

if j n then

begin

if f > a+f then begin f:=a+f; re:=j; end;

if f > a+f then begin f:=a+f; re:=j+1; end;

end;

end;

难度为1 汗

交了18次才ac

鉴定完毕：我菜！

对于此题,我无语了...

好郁闷啊。。

一直都只有67分。。

呜呜··编译通过...

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

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

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

　├ 错误行输出

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

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

　├ 错误行输出

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

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

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

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

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

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

郁闷死了··。。

呜呜··

编译通过...

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

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

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

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

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

　├ 错误行输出 499

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

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

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

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

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

Unaccepted 有效得分：78 有效耗时：310ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

路径输出似乎没有之前的大牛说得那么恶心。

dp就不说了，牛们已经重复多遍了。

我在dp的时候不停的维护每个点的前驱，然后最后找到最后一层的最小值，从那个点倒推回去，输出路径就完了。好像也没判断什么长度最小的路径。

如果有地方不妥，请各位大牛指正

编译通过...

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

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

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

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

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

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

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

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

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

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

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

郁闷！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

猥琐啊！Vijos真正是我见过的评测数据最猥琐的OJ！

解法前面的大牛们已经讲得很清楚了，我就不再重复了。

我只想提请还没有AC的同志们注意一点，原题虽然说“随便输出一条路径即可”，但动脑子想想，现在的OJ还达不到能使多种结果都正确的水平，换句话说，正确答案只有一个，依经验，这一条应该是代价最小且路程最短的路径。

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

我要是不这么干，4、5两点总是wa掉，78分；加上判断最短路径才AC,偶可怜的AC率啊~~~~

测试数据答案是所有可行解中字典排序最大的

!!!!

太简单了，不想做了

spfa

先将第M层所有顶点放进去，D:=cost(s);

边权什么的自己搞。

最后求最短路

ft……答案不唯一，又没有special judge……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

真是笨死了，看了楼上的恍然大悟，来回扫描一次即可，不过还是三点不明：

1）此题数据如何，按题意怎么计算都超不了int64，可是看看如此低的通过率实在有点怀疑是否需要高精

2）楼上的楼上用的是什么算法，好奇

3）是否本人悟性太低，第一次看到输出的

3

3

2

1

1

我愣了好久

此题满足单调性！

对于同行只须左右各扫描一次即可！

因为无负权！向右再向左只会增加费用！

SPFA也可以？？不超时？？郁闷

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

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

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

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

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

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

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

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

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

初学DP还不上手 不能0ms AC

再接再厉

小技巧：来回搜两遍，取消后效性。。。。。。。

程序输出比正确答案长是什么意思啊~~

为什么非要从顶楼DP到底楼,而底楼DP到顶楼为什么错?

小弟在前辈WA3 WA5 TEL8的牺牲下，2次AC了此题

一次AC 的题目,不知道为什么AC率这么低.......

我是正读的.......SPFA