lyzqs的博客

算是我做过的比较容易的一道动态规划了吧

因为后效性的缘故，只能用鼹鼠做状态

然后考虑转移

每个鼹鼠可以从前面的任何一个转移过来

初始化ans=1,f[i]=1

然后就没了

#include <bits/stdc++.h>
#define il inline
#define Max 100005
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
using namespace std;
char In[Max],*ss=In,*tt=In;
namespace lyzqs
{
    il int read()
    {
        char c=getchar();
        int x=0,f=1;
        while(c>'9'||c<'0')
        {
            if(c=='-') f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            x=x*10+c-'0';
            c=getchar();
        }
        return x*f;
    }
    int n,m,f[Max],ans=1;
    struct node
    {
        int t,x,y;
    }e[Max];
    il int dis(int i,int j)
    {
        return abs(e[i].x-e[j].x)+abs(e[i].y-e[j].y);
    }
    void main()
    {
        n=read(),m=read();
        for(int i=1;i<=m;i++)
        {
            f[i]=1;
            e[i].t=read(),e[i].x=read(),e[i].y=read();
            for(int j=1;j<=i-1;j++)
            {
                if(dis(i,j)<=e[i].t-e[j].t)
                    f[i]=max(f[i],f[j]+1),ans=max(ans,f[i]);
            }
        }
        cout<<ans<<endl;
    }
}
int main()
{
    lyzqs::main();
}