38 条题解
-
1
搬运工 (syrth0p1) LV 10 @ 2025-06-25 14:00:15
#include <iostream> #include <cstdio> #define INF 0x3f3f3f #include <cstring> #include <algorithm> using namespace std; int C,H,B; const int maxc = 1050, maxh = 1050; int f[maxc][maxc][2]; struct node{ int x, t; bool operator < (const node &b)const{ return x < b.x; } }a[maxc]; int main(){ cin>>C>>H>>B; for(int i = 1; i <= C; i++){ cin>>a[i].x>>a[i].t; } sort(a + 1, a + 1 + C); memset(f, INF,sizeof(f)); f[1][C][0] = max(a[1].x,a[1].t); f[1][C][1] = max(a[C].x,a[C].t); for(int i = 1; i <= C; i++){ for(int j = C; j >= i; j--){ f[i][j][0] = min(f[i][j][0], max(f[i - 1][j][0] + a[i].x - a[i - 1].x, a[i].t) ); f[i][j][0] = min(f[i][j][0], max(f[i][j + 1][1] + a[j + 1].x - a[i].x, a[i].t) ); f[i][j][1] = min(f[i][j][1], max(f[i][j + 1][1] + a[j + 1].x - a[j].x, a[j].t) ); f[i][j][1] = min(f[i][j][1], max(f[i - 1][j][0] + a[j].x - a[i - 1].x, a[j].t) ); } } int ans = INF; for(int i=1;i<=C;i++) { ans = min(ans,min(f[i][i][0]+abs(a[i].x - B), f[i][i][1] + abs(a[i].x-B))); } cout<<ans; }
-
02010-04-13 15:56:07@
mbssn
-
02010-04-09 18:20:42@
orz宋神牛
-
02010-04-04 08:23:48@
这题太恶搞了。。。。
-
02010-03-01 11:01:39@
哈哈,搞笑。
-
02009-11-06 10:34:43@
cool
-
02009-10-23 21:06:37@
编译通过...
├ 测试数据 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 -
02009-10-20 10:38:57@
USACO 04OPEN GREEN改的啊
-
02009-10-08 17:05:54@
看来DP还是要考虑答案的单调性= =
OTZ大牛们
-
02009-10-06 13:42:28@
哪有满分???各位不是做梦呢吧???偶还没听说过满分神牛呢。。。。
只知道IMO有个韦东奕的神牛,参加几次IMO,都是满分。。。。。 -
02009-10-04 12:37:10@
神经题
-
02009-10-01 16:05:50@
边界好重要啊,第0个位置也要考虑,数组范围要多开1~~
-
02009-09-18 19:38:00@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
02009-09-15 11:54:42@
感谢楼上的陈大牛给我鼓励
-
02009-09-14 20:24:03@
1.边界
2.想清楚几个细节
3.重要的性质 -
02009-08-06 16:06:51@
囧啊囧,囧啊囧,囧得下巴也掉了 冏
-
02009-07-25 08:50:27@
一坨一坨,说话怎么那么像“铝箱”啊
-
02009-07-21 21:47:38@
这性质可真是有很大用处啊!
orz oimaster 和 voyagec2 !
友情提示:可能第零个位置也要交作业……(位置是个非负数……)
被阴了一次…… -
02009-07-20 19:13:14@
终于AC了..
注意边界. -
02009-07-20 18:07:27@
千万不要写记忆化!!!
voyagec2每次写题解写得都很详细
给我们菜鸟提供了很多帮助,在这里maxqword谢谢他