维和部队题解

维和部队

题目描述
在2019国庆大阅兵仪式上，蓝色贝雷帽，荒漠迷彩服，维和部队方队阔步走来。中国是联合国安理会常任理事国中派出维和人员最多的国家。在联合国7个维和任务区，2500多名中国军人守护在最危险的地方，还有8000名维和待命官兵随时听令出征。中国无战事，军人有牺牲。先后有13名维和勇士牺牲在异国他乡，中国军人用生命和热血彰显维护世界和平的大国担当！向维和部队官兵致敬！向中国军人致敬！
现在，维和部队每天都收到很多的维和任务命令，假设维和部队所在的维和区域可以抽象为一个N*N大小的矩阵形区域，并且认为矩阵形区域的左上角坐标为<1,1>，右下角坐标为<N,N>。现在联合国军事指挥所开始陆续地在我维和区域下达维和任务的命令，命令格式如下(详见数据样例)：
TIME ROW COL
该命令格式解读为：在TIME时刻，在矩阵形区域的<ROW,COL>坐标处有一个维和任务，如果要完成该任务，部队必须在TIME时刻到达这里，也就是说，如果维和部队到达<ROW,COL>的时刻不是TIME，则认为这个任务失败。现在维和部队正乘坐武装直升机在维和区域上空待命，他们随时准备空降到矩形区域的任何一个点上，假设空降到地面的时刻为1时刻，落地之后每过一个时间单位，他们只能向直接相邻的上、下、左、右四个方向移动一个距离单位，或者保持在原地不动。维和区域情况非常复杂，每一个维和任务确实不一定能够完成，现在你作为我维和部队的参谋长，请你根据维和任务数据和规则，计算在给定的任务中做多能够完成几个？
输入格式
第一行输入两个正整数N, M，空格分隔，分别代表矩形区域的大小和维和任务数量，1<=N<=1000，1<=M<=10000
接下来M行每行三个数，空格分隔，代表在时刻TIME，矩形区域的横坐标ROW，纵坐标COL处有一个任务。
数据保证任何两个任务都是不同的，同一时刻最多只有一个任务命令。
输出格式
输出维和部队最多能够完成的任务数量。输出数据完成后输出回车换行。
输入样例 复制
7 7
3 6 3
4 4 7
5 7 3
1 5 3
2 3 5
7 1 3
6 2 3
输出样例 复制
3
解题思路：
这题的19包师校赛题最开始看见这个题的时候 以为是要建一个二维数组 然后搜索… 尽力了 没搞出来 看着以前的校赛题解 不对劲啊 这不是一个搜索呀 这是一个贪心问题吧 做尽可能多的任务嘛 是动态规划 又现从网上学的lis 上图！


就像题解中说的这是个动态规划问题，LIS变形题，按时间排序，时间差允许范围内去多做 一个任务。 在代码里有详细的注释
以下是AC代码：

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
//这个题 最开始理解错题意了  这里的 time 可不是在什么时间要完成什么 而是说 完成当前任务后 在到下一个任务点所限定的时间 
struct grid{
	int t;
	int x;
	int y;
}g[1005];
//这个数组 是我们一会要用lis（最大上升子序列）需要的 
int dp[1005];

bool cmp(grid a , grid b){
	return a.t < b.t;
}

int main(){
	int n,m;
	int i,j,k;
	while(cin>>n>>m){
		
		for(i=1;i<=m;i++){
			cin>>g[i].t>>g[i].x>>g[i].y;
		}
		//为什么要sort排序呢  因为 我们想要做的是在时间差允许的范围内做尽可能多的任务！
		//贪心！   这次的sort都加了1 是因为我在输入的时候就是从i=1开始输入的 半闭半开区间嘛 
		sort(g+1,g+m+1,cmp);
		//这个变量是来存最多能完成多少任务的 只要存个负数 或者  0  都行  因为极端情况就是没有任务呗 其实0就足够了 
		int ans = -1;
		//其实这两个循环就是 lis 的写法   只不过就是多加了判断 
		
		//在这道题目中其实他已经变相跟你说了 没有别的坑了  我从天上往地下飞 也得需要1个time呢！ 所以最开始不要多想 
	 
		for(i=1; i<=m; i++){ 
			dp[i] = 1;
			for(j=1;j<i;j++){
				//因为你每移动一个单位的距离就要消耗1time 
				int time = abs(g[i].x-g[j].x) + abs(g[i].y-g[j].y);
				//虽然题目说了 不是在t时刻到达就不行  但是要注意的是 题目也说了 我也可以瞎tm逛悠 所以t要小于等于 
				if(time<=abs(g[i].t-g[j].t))
				dp[i] = max(dp[i],dp[j]+1);
			} 
			//因为lis算法可不是dp[最大下标]就最大   如0 1 2 5 0   最大子序列长度是4   dp[3]==4  dp[4]==1 
			ans = max(ans,dp[i]);
		} 
		cout<<ans<<endl;
	}
	return 0;
}