题解 - Vijos

0
man75319 LV 3 @ 2007-11-11 16:25:42

看完后~~~~~~小弟不胜感激~~~~~~~太棒了
0
luanjiyang LV 3 @ 2007-11-08 10:35:33

很委琐的提交了6遍
0
ldg000 LV 3 @ 2007-10-31 18:21:29

我看奥赛经典里讲二取方格数，两条路除了起点和终点，中间一定无交点。我觉得这题应该也是这样，除了第一阶段，第二阶段，倒数第一阶段，倒数第二阶段，其余无交点。因为如果有交点，那么一定有其他走法，使其中一条路绕过去走，比有交点的更优或相同（因为方格数都是不小于零的）。我这样做，AC了，我想应该没问题。
0
xmyzxsxy LV 7 @ 2007-10-31 15:39:08

f[k,n,m,r]

设这三个人同时走

注意到只能向下走或向右走

设第i次走完的坐标为(x,y)

那么有 x+y = k-1

所以，在状态中不需要将x,y加入状态中

那么再想想这一步是怎么走来的呢？

ps:其实一开始看这题想到的是O(N^6)的
0
fluorine LV 3 @ 2007-10-28 23:46:03

为什么只能过前三个数据？
0
gamejifan LV 7 @ 2007-10-15 22:36:52

注意数组不要开小，虽然n是20，但是dp起来那就要开至少40了。
0
yaonie LV 3 @ 2007-09-29 21:39:20

感谢　KKKing　同学

一次ＡＣ．．
0
wenyue LV 3 @ 2007-09-10 22:02:37

原来我看错数据了，把Ｎ看成８０，用了个滚动数组，繁啊～～～～～～～～～
0
zzyynn LV 4 @ 2007-09-08 10:30:49

是的啊，阶段的划分太牛了！！！
0
西碧儿 LV 3 @ 2007-08-21 09:43:02

由于没做二取方格数；我一开始用一般DP；DP一次则把走过的路删去；3次DP；

只对了一组；

后来做了二取方格数；才知道我的算法虽然保证了3次DP的最优；但并不代表全局最优；是有反例的......
0
the_melody LV 3 @ 2007-08-20 21:41:06

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

晕`\不是0ms
0
sm-star LV 3 @ 2007-08-20 14:13:04

我做得像个超级01背包
0
yours LV 7 @ 2007-08-10 14:43:46

动态规划
0
.FRA-泽 LV 3 @ 2007-08-04 09:24:47

明显的动规.最主要的是划分阶段.斜着划~~~
0
ljj5112898 LV 3 @ 2007-08-03 10:54:38

Alexandria在刷屏吗？

。。。

确实是网络流的题，但是俺不会编。

数据弱，DP一样能过。
0
donglixp LV 3 @ 2007-07-26 20:55:09

原来是这样！
0
梦在飞翔 LV 3 @ 2007-04-29 22:35:27

最小费用最大流...
0
宇宙新秀 LV 3 @ 2006-11-06 19:51:03

改成n取方格数把，那多有意思啊。。。。。。。
0
渴望奔跑的鱼 LV 3 @ 2006-10-28 15:07:27

这道题状态划分比较重要！~！
0
cool_leaf_xp LV 3 @ 2006-10-27 17:44:19

如果是取Ｎ次怎么办？

ID

1143

难度

4

分类

动态规划点击显示

标签

递交数

已通过

1452

通过率

41%

被复制

9

上传者