题解

83 条题解

  • 1
    @ 2018-11-04 17:33:03
    //这道题我们首先有一个O(n*n*m)的暴力DP,然后它死了
    //接下来考虑优化
    //其实我们根本不考虑某一时刻机器人在哪,我们只要确保它能到一个位置就好了
    //于是可以对于每一只老鼠,我们枚举机器人上一只打的是谁
    //于是我们有了O(m*m)的算法
    #include<cstdio>
    using namespace std;
    int dp[10010],x[10010],y[10010],t[10010];
    int Abs(int x)
    {
        if(x>0)
         return x;
        return -x;
    }
    int Max(int x,int y)
    {
        if(x>y)
         return x;
        return y;
    }
    int main()
    {
        int n,m,i,j,ans=0;
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&t[i],&x[i],&y[i]);
            dp[i]=1;
            for(j=1;j<i;j++)
             if(Abs(x[i]-x[j])+Abs(y[i]-y[j])<=t[i]-t[j])
              dp[i]=Max(dp[i],dp[j]+1);
        }
        for(i=1;i<=m;i++)
         ans=Max(ans,dp[i]);
        printf("%d",ans);
        return 0;
    }
    
  • 0
    @ 2014-09-29 13:22:04

    const
    maxn=1000;
    maxm=10010;
    var
    t,x,y:array[0..maxm]of longint;
    f,next:array[0..maxm]of longint;
    n,m,ans:longint;

    function max(x,y:longint):longint;
    begin
    if x>y then exit(x);
    exit(y);
    end;

    procedure init;
    var
    i,tot:longint;
    begin
    read(n,m);
    tot:=0;
    for i:=1 to m do
    begin
    inc(tot);
    read(t[tot],x[tot],y[tot]);
    if (x[tot]<=0)or(x[tot]>n)or(y[tot]<=0)or(y[tot]>n) then dec(tot);
    end;
    m:=tot;
    next[0]:=m+1;
    end;

    procedure work;
    var
    i,j,k:longint;
    begin
    for i:=1 to m do
    begin
    j:=0;
    k:=0;
    while next[j]<>m+1 do
    begin
    if t[i]-t[next[j]]>=abs(x[i]-x[next[j]])+abs(y[i]-y[next[j]]) then break;
    if f[next[j]]<f[j] then k:=j;
    j:=next[j];
    end;
    f[i]:=f[next[j]]+1;
    next[i]:=next[k];
    next[k]:=i;
    ans:=max(ans,f[i]);
    end;
    writeln(ans);
    end;

    begin
    init;
    work;
    end.

  • 0
    @ 2014-09-07 16:36:35

    用longlong竟然超时,用龙就过了。。。。。

  • 0
    @ 2014-08-16 19:41:16

    program p1441;
    var
    a,b,t,f:array[1..10000]of longint;
    i,j,n,m,ans:longint;
    begin
    filldword(f,sizeof(f)shr 2,1);
    readln(n,m);
    for i:=1 to m do readln(t[i],a[i],b[i]);
    for i:=1 to m do for j:=1 to i-1 do
    if (abs(a[j]-a[i])+abs(b[j]-b[i])<=(t[i]-t[j]))and(f[j]+1>f[i])
    then f[i]:=f[j]+1;
    for i:=1 to m do if f[i]>ans then ans:=f[i];
    writeln(ans);
    end.
    15行

  • 0
    @ 2013-11-02 09:16:48

    农夫山泉有点甜。
    我看楼上有些大神都是0ms秒杀的……汗……
    本人比较朴素,所以写法上复杂度有点高,不过还是过了,哈哈!
    补充:下面的代码有残缺,要自己写哦!
    var
    i,j,k,m,n,max:longint;
    a:array[1..10000,1..2] of longint;
    b,c:array[0..10000] of longint;
    begin
    readln(n,m);
    for i:=1 to m do readln(c[i],a[i,1],a[i,2]);
    for i:=1 to m do b[i]:=1;
    for i:=1 to m do
    for j:=1 to i-1 do
    begin
    if ((abs(a[j,1]-a[i,1])+abs(a[j,2]-a[i,2]))<=(c-c))and(a[i,1]<=n)
    and(a[i,2]<=n)and(a[i,1]>0)and(a[i,2]>0)and(b[j]+1>b[i])
    then b[i]:=b[j]+1;
    end;
    for i:=1 to m do if b[i]>max then max:=b[i];
    writeln(max);
    end.

  • 0
    @ 2013-10-27 18:50:08

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 976 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 980 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 976 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 980 KiB, score = 10
    测试数据 #4: Accepted, time = 31 ms, mem = 980 KiB, score = 10
    测试数据 #5: Accepted, time = 31 ms, mem = 976 KiB, score = 10
    测试数据 #6: Accepted, time = 42 ms, mem = 980 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 980 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 980 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 980 KiB, score = 10
    Accepted, time = 134 ms, mem = 980 KiB, score = 100
    YES!下面为题解

  • 0
    @ 2013-10-27 18:49:04

    能绝对AC
    type
    node=record
    f,t,x,y:longint;
    end;
    var max,i,j,n,m:longint;
    t:node;
    a:array[0..10000]of node;
    begin
    readln(n,m);
    for i:=1 to m do readln(a[i].t,a[i].x,a[i].y);
    for i:=1 to m do
    begin
    max:=0;
    for j:=i-1 downto 1 do
    if a[j].f>=max then
    begin
    if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)<=a[i].t-a[j].t)then
    max:=a[j].f;
    end
    else break;
    a[i].f:=max+1;
    j:=i;
    while a[j].f<a[j-1].f do begin t:=a[j];a[j]:=a[j-1];a[j-1]:=t;dec(j);end;
    end;
    write(a[m].f);
    end.

  • 0
    @ 2012-07-27 13:35:33

    这道题其实是湖南省选的原题

  • 0
    @ 2009-11-14 10:19:45

    记录号 Flag 得分 记录信息

    R1745955 Accepted 100 From 国防安全员001- P1441

    环境 评测机 程序提交时间

    FPC Evolution SmdCn 2009-11-14 10:17:18

    编译通过...

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

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

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

    ├ 测试数据 04:答案正确... 400ms

    ├ 测试数据 05:答案正确... 384ms

    ├ 测试数据 06:答案正确... 478ms

    ├ 测试数据 07:答案正确... 572ms

    ├ 测试数据 08:答案正确... 462ms

    ├ 测试数据 09:答案正确... 525ms

    ├ 测试数据 10:答案正确... 431ms

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

    Accepted 有效得分:100 有效耗时:3252ms

  • 0
    @ 2009-10-31 21:48:07

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    转移方法见楼下

    f[i]:=f[j]+1 (abs(x[i]-x[j])+abs(y[i]-y[j])

  • 0
    @ 2009-10-30 21:26:04

    此题很经典啊

    f[i]:=f[j]+1 (abs(x[i]-x[j])+abs(y[i]-y[j])=max 一定要有等号! 0.2s

    此题总结:神题!Orz...

    结合了三种优化方法一次秒杀:状态、方向和决策

    ————————————————————

    以上是我为此题写给自己的总结

    以此纪念此题的各种状态和优化

    可能写得不清楚……

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    比神牛的短一点吧~~~

    type

    node=record

    f,t,x,y:longint;

    end;

    var

    max,i,j,n,m:longint;

    t:node;

    a:array[0..10000]of node;

    begin

    assign(input,'mole.in');reset(input);

    assign(output,'mole.out');rewrite(output);

    readln(n,m);

    for i:=1 to m do readln(a[i].t,a[i].x,a[i].y);

    close(input);

    for i:=1 to m do

    begin

    max:=0;

    for j:=i-1 downto 1 do

    if a[j].f>=max then

    begin

    if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)

  • 0
    @ 2009-10-28 19:34:36

    编译通过...

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

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

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

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

    ├ 测试数据 05:答案正确... 119ms

    ├ 测试数据 06:答案正确... 88ms

    ├ 测试数据 07:答案正确... 72ms

    ├ 测试数据 08:答案正确... 72ms

    ├ 测试数据 09:答案正确... 88ms

    ├ 测试数据 10:答案正确... 134ms

    果真,顺推3个点,逆推就磕磕绊绊过了,虽然没秒,但是快很多啊!

  • 0
    @ 2009-10-18 20:35:16

    难道倒着循环 比 正着循环快那么多~~???!!神奇~~~~

    C++注意输入输出 及 常数级的优化

    没想到这么个常数优化吗m^2的就过了。。。。。

  • 0
    @ 2009-09-25 09:09:16

    编译通过...

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

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

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

    ├ 测试数据 04:答案正确... 25ms

    ├ 测试数据 05:答案正确... 25ms

    ├ 测试数据 06:答案正确... 41ms

    ├ 测试数据 07:答案正确... 9ms

    ├ 测试数据 08:答案正确... 25ms

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

    ├ 测试数据 10:答案正确... 56ms

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

    Accepted 有效得分:100 有效耗时:222ms

    同样的程序,PUPPY与SUNNY真得没法比

  • 0
    @ 2009-09-10 22:21:32

    编译通过...

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

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

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

    ├ 测试数据 04:答案正确... 509ms

    ├ 测试数据 05:答案正确... 509ms

    ├ 测试数据 06:答案正确... 494ms

    ├ 测试数据 07:答案正确... 509ms

    ├ 测试数据 08:答案正确... 509ms

    ├ 测试数据 09:答案正确... 494ms

    ├ 测试数据 10:答案正确... 509ms

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

    Accepted 有效得分:100 有效耗时:3533ms

  • 0
    @ 2009-08-19 18:54:20

    类似于导弹拦截。

    宋氏优化太神奇了,我太弱菜,实在配不上用。

  • 0
    @ 2009-08-13 08:21:43

    极其严重之膜拜curimit宋神牛之无敌优化

  • 0
    @ 2009-08-10 14:37:54

    var

    n,m,shijian,heng,zong,i,j,max:longint;

    a,x,y,zhouoi:array[-10..10000]of longint;

    begin

    readln(n,m);

    for i:=1 to m do

    begin

    readln(a[i],x[i],y[i]);

    end;

    for i:=1 to m do

    begin

    for j:=i downto 1 do

    begin

    if (a[i]-a[j]>=abs(x[i]-x[j])+abs(y[i]-y[j]))

    and(zhouoi[j]+1>zhouoi[i])

    then begin zhouoi[i]:=zhouoi[j]+1;

    if max

  • 0
    @ 2009-07-05 17:15:25

    尽然没秒kill????????????????????????????????

    o(╯□╰)o

  • 0
    @ 2009-06-16 08:46:42

    严重膜拜curimit神牛的优化方法!太强大了!

信息

ID
1441
难度
5
分类
动态规划 点击显示
标签
递交数
810
已通过
277
通过率
34%
被复制
2
上传者