首页 > 代码库 > 1207: [HNOI2004]打鼹鼠(DP)

1207: [HNOI2004]打鼹鼠(DP)

2024-09-18 21:45:15   206人阅读

Description

鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏：在一个nn的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为（i,j）的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格，机器人不能走出整个nn的网格。游戏开始时，你可以自由选定机器人的初始位置。现在你知道在一段时间内，鼹鼠出现的时间和地点，希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

Input

第一行为n（n<=1000）, m（m<=10000），其中m表示在这一段时间内出现的鼹鼠的个数，接下来的m行每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻，在第x行第y个网格里出现了一只鼹鼠。Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。

Output

仅包含一个正整数，表示被打死鼹鼠的最大数目

Sample Input

2 21 1 12 2 2

Sample Output

1

技术分享

Code:

技术分享
 1 #pragma comment(linker, "/STACK:36777216") 2  3 #include <bits/stdc++.h> 4 using namespace std; 5 #define LSON            id << 1 , l , mid 6 #define RSON            id << 1 | 1 , mid + 1 , r 7 #define ROOT            1 , 1 , n 8 #define CLR(x , y)      memset(x , y , sizeof(x)) 9 #define LOWBIT(x)       x & (-x)10 #define FORN(i , a , n)  for(int i = (a) ; i <= (n) ; ++i)11 #define FORP(i , n , a)  for(int i = (n) ; i >= (a) ; --i)12 #define CASE(x)        printf("Case %d: ", x)13 #define SFD(x)      scanf("%lf" , &x)14 #define SFC(x)      scanf(" %c" , &x)15 #define SFS(x)      scanf(" %s" , x)16 #define SFI(x)      scanf("%d" , &x)17 #define SFI64(x)    scanf("%I64d" , &x)18 #define PFF(x)         printf("%f" , x)19 #define PFD(x)         printf("%lf" , x)20 #define PFI(x)         printf("%d" , x)21 #define PFC(x)         printf("%c" , x)22 #define PFS(x)         printf("%s" , x)23 #define PFI64(x)       printf("%I64d" , x)24 #define SPACE          printf(" ")25 #define PUT            puts("")26 #define LPUP(i , j , k) for(int i = j ; i <= k ; ++i)27 #define LPDW(i , j , k) for(int i = j ; i >= k ; --i)28 #define PB(x)          push_back(x)29 #define ALL(A)         A.begin(), A.end()30 #define SZ(A)          int((A).size())31 #define LBD(A, x)      (lower_bound(ALL(A), x) - A.begin())32 #define UBD(A, x)      (upper_bound(ALL(A), x) - A.begin())33 #define LOCAL34 static const double PI = acos(-1.0);35 static const double EPS = 1e-8;36 static const int INF = 0X3fffffff;37 typedef long long LL;38 typedef double DB;39 template<class T> inline40 void read(T &x)41 {42     x = 0;43     int f = 1 ; char ch = getchar();44     while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();}45     while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();}46     x *= f;47 }48 49 /************************Little Pea****************************/50 51 static const int MAXN = 1e5 + 10;52 int x[MAXN] , y[MAXN] , t[MAXN];53 int dp[MAXN];54 int n , m;55 int main()56 {57 #ifndef ONLINE_JUDGE58     //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin);59 #endif60     read(n);read(m);61     LPUP(i , 1 , m) dp[i] = 1;62     LPUP(i , 1 , m)63     {64         read(t[i]);read(x[i]);read(y[i]);65         LPUP(j , 1 , i - 1)66         {67             if(abs(x[i] - x[j]) + abs(y[i] - y[j]) <= t[i] - t[j])68                 dp[i] = max(dp[i] , dp[j] + 1);69         }70     }71     PFI(*max_element(dp + 1 , dp + 1 + m));72 73 #ifndef ONLINE_JUDGE74     fclose(stdin), fclose(stdout);75 #endif76 }
View Code

 

1207: [HNOI2004]打鼹鼠(DP)


联系
我们