题解 - Vijos

0
aaaaaaa LV 7 @ 15 年前

mbssn
0
wll969 LV 8 @ 15 年前

orz宋神牛
0
181818181818 LV 10 @ 15 年前

这题太恶搞了。。。。
0
curimit LV 10 @ 15 年前

哈哈，搞笑。
0
小弟不才 LV 8 @ 15 年前

cool
0
huyou0616 LV 8 @ 15 年前

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Accepted 有效得分：100 观察一个事实：

假设最优路线是这么走的：

先从0走到r1，在r1处掉头，再从r1走到l1，在l1处转头，走到r2„„

则一定有： 0≤l1
0
@yxw@ LV 10 @ 15 年前

USACO 04OPEN GREEN改的啊
0
fp_yfw LV 10 @ 15 年前

看来DP还是要考虑答案的单调性= =

OTZ大牛们
0
ssxyh LV 9 @ 15 年前

哪有满分？？？各位不是做梦呢吧？？？偶还没听说过满分神牛呢。。。。

只知道IMO有个韦东奕的神牛，参加几次IMO，都是满分。。。。。
0
flower LV 8 @ 15 年前

神经题
0
new world LV 10 @ 15 年前

边界好重要啊，第0个位置也要考虑，数组范围要多开1~~
0
yzl609271536 LV 10 @ 15 年前

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Accepted 有效得分：100 有效耗时：0ms
0
jacklv LV 10 @ 15 年前

感谢楼上的陈大牛给我鼓励
0
陈亮宇 LV 10 @ 15 年前

1.边界

2.想清楚几个细节

3.重要的性质
0
ccw630 LV 10 @ 15 年前

囧啊囧，囧啊囧，囧得下巴也掉了冏
0
飞翔 LV 10 @ 15 年前

一坨一坨，说话怎么那么像“铝箱”啊
0
唐钰小宝 LV 10 @ 15 年前

这性质可真是有很大用处啊！

orz oimaster 和 voyagec2 ！

友情提示：可能第零个位置也要交作业……（位置是个非负数……）

被阴了一次……
0
Havenking LV 8 @ 15 年前

终于AC了..

注意边界.
0
yxyddd LV 10 @ 15 年前

千万不要写记忆化!!!

voyagec2每次写题解写得都很详细

给我们菜鸟提供了很多帮助,在这里maxqword谢谢他
0
ben123456 LV 8 @ 15 年前

我是很少上网做题的，说的不对大家见谅......

这题刚开始时看见是DP的确有点悬念......

其实宋神牛交作业的地点有N个,首先按地点从小到大排序,如果要交第i个地点的作业，那么宋神牛肯定要把1至i-1的作业或者先把i+1至n的作业做完才做第i个作业，这样才会有一个最优解。

所以可以列方程f=f+i地点和j地点的距离；

i,j是宋神牛已经做完1至i-1和j+1至n的作业，l记录是送神牛在第i位或者第j位。

还有f:=min(f,f+i地点和j地点的距离),因为宋神牛可能从i到j或者从j到i。

最后f就是是宋神牛最后做第i作业的最小时间，贪心一下就行了。。。。