bzoj 1207: [HNOI2004]打鼹鼠【dp】

跟简单的dp，设f[i]表示前i只最多打几只，因为起点不确定，所以f[i]可以从任意abs(x[i]-x[j])+abs(y[i]-y[j])<=abs(time[i]-time[j])的j<i转移：f[i]=max(f[j]+1);

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

const int N=10005;

int n,m,x[N],y[N],z[N],f[N],ans=1,tot;

int read()

{

    int r=0,f=1;

    char p=getchar();

    while(p>'9'||p<'0')

    {

        if(p=='-')

            f=-1;

        p=getchar();

    }

    while(p>='0'&&p<='9')

    {

        r=r*10+p-48;

        p=getchar();

    }

    return r*f;

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<=m;i++)

    {

        int a=read(),b=read(),c=read();

        if(c<=n&&c>=1&&b<=n&&b>=1)

			z[++tot]=a,x[tot]=b,y[tot]=c;

    }

    for(int i=1;i<=m;i++)

		f[i]=1;

    for(int i=2;i<=tot;i++)

    {

        for(int j=1;j<i;j++)

			if(abs(x[i]-x[j])+abs(y[i]-y[j])<=abs(z[i]-z[j]))

				f[i]=max(f[i],f[j]+1);

        ans=max(ans,f[i]);

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

bzoj 1207: [HNOI2004]打鼹鼠【dp】

最新文章

热门文章