bzoj1207,懒得复制，戳我戳我

Solution:

• 挺傻逼的一个\(dp\)，直接推就好了
• 这题在bzoj上的数据有点问题，题目保证每个时间点不会出现在同一位置两个地鼠，然而他有= =（还浪费我20分钟差错

Code:

• \(luogu\) AC代码:

//It is coded by Ning_Mew on 5.6

#include<bits/stdc++.h>

using namespace std;

const int maxm=1e4+7;

int n,m;

int x[maxm],y[maxm],t[maxm];

int dp[maxm],ans=0;

int main(){

  scanf("%d%d",&n,&m);

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

    scanf("%d%d%d",&t[i],&x[i],&y[i]);

    dp[i]=1;

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

      if(t[j]==t[i])break;

      if(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]) dp[i]=max(dp[i],dp[j]+1);

    }

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

  }

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

  return 0;

}

• \(bzoj\) AC 代码:

//It is coded by Ning_Mew on 5.6

#include<bits/stdc++.h>

#define RE register

using namespace std;

const int maxm=1e4+7;

int n,m;

int x[maxm],y[maxm],t[maxm];

int dp[maxm],ans=0;

int main(){

  scanf("%d%d",&n,&m);

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

    scanf("%d%d%d",&t[i],&x[i],&y[i]);

    dp[i]=1;

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

      //if(t[j]==t[i])break;

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

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

    }

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

  }

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

  return 0;

}