38 条题解

  • 1
    @ 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;
    }
    
  • 0
    @ 2010-04-13 15:56:07

    mbssn

  • 0
    @ 2010-04-09 18:20:42

    orz宋神牛

  • 0
    @ 2010-04-04 08:23:48

    这题太恶搞了。。。。

  • 0
    @ 2010-03-01 11:01:39

    哈哈,搞笑。

  • 0
    @ 2009-11-06 10:34:43

    cool

  • 0
    @ 2009-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

  • 0
    @ 2009-10-20 10:38:57

    USACO 04OPEN GREEN改的啊

  • 0
    @ 2009-10-08 17:05:54

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

    OTZ大牛们

  • 0
    @ 2009-10-06 13:42:28

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

    只知道IMO有个韦东奕的神牛,参加几次IMO,都是满分。。。。。

  • 0
    @ 2009-10-04 12:37:10

    神经题

  • 0
    @ 2009-10-01 16:05:50

    边界好重要啊,第0个位置也要考虑,数组范围要多开1~~

  • 0
    @ 2009-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

  • 0
    @ 2009-09-15 11:54:42

    感谢楼上的陈大牛给我鼓励

  • 0
    @ 2009-09-14 20:24:03

    1.边界

    2.想清楚几个细节

    3.重要的性质

  • 0
    @ 2009-08-06 16:06:51

    囧啊囧,囧啊囧,囧得下巴也掉了 冏

  • 0
    @ 2009-07-25 08:50:27

    一坨一坨,说话怎么那么像“铝箱”啊

  • 0
    @ 2009-07-21 21:47:38

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

    orz oimaster 和 voyagec2 !

    友情提示:可能第零个位置也要交作业……(位置是个非负数……)

    被阴了一次……

  • 0
    @ 2009-07-20 19:13:14

    终于AC了..

    注意边界.

  • 0
    @ 2009-07-20 18:07:27

    千万不要写记忆化!!!

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

    给我们菜鸟提供了很多帮助,在这里maxqword谢谢他

信息

ID
1576
难度
7
分类
动态规划 点击显示
标签
(无)
递交数
257
已通过
51
通过率
20%
被复制
2
上传者