首页 > 代码库 > [bzoj1207][HNOI2004]打鼹鼠

[bzoj1207][HNOI2004]打鼹鼠

 

有一个n*n的网格图,有m只鼹鼠,每只都有一个出现时间t,坐标(x,y),你有一个机器人,如果鼹鼠出现的时候你在那里就可以打死他,但是每1单位时间只能移动1格,求最多能打死多少鼹鼠.....m<=10000

 题解:m^2暴力dp啊

我真的只是按照ac顺序排了个序,不是刷水啊...

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<0||ch>9){if(ch==-) f=-1;ch=getchar();}
    while(ch>=0&&ch<=9){x=x*10+ch-0; ch=getchar();}
    return x*f;
}

int t[10005],x[10005],y[10005],n,m,f[10005],ans=0;
inline int abs(int x){return x<0?-x:x;}

int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)t[i]=read(),x[i]=read(),y[i]=read();
    for(int i=1;i<=m;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)if(abs(x[i]-x[j])+abs(y[i]-y[j])<=(t[i]-t[j])) f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}

然后发现别人跑的飞快,去黄学长博客看了一下,原来是玄学优化.....

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<0||ch>9){if(ch==-) f=-1;ch=getchar();}
    while(ch>=0&&ch<=9){x=x*10+ch-0; ch=getchar();}
    return x*f;
}

int t[10005],x[10005],y[10005],n,m,f[10005],ans=0,mx[10005];
inline int abs(int x){return x<0?-x:x;}

int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)t[i]=read(),x[i]=read(),y[i]=read();
    for(int i=1;i<=m;i++)
    {
        f[i]=1;
        for(int j=i-1;j;j--)if(mx[j]+1<f[i])break;
        else if(abs(x[i]-x[j])+abs(y[i]-y[j])<=(t[i]-t[j])) f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);mx[i]=max(mx[i-1],f[i]);
    }
    cout<<ans;
    return 0;
}

一个2500+ms,一个36ms.......

[bzoj1207][HNOI2004]打鼹鼠