cspj2022 T4 上升点列(point)题解（floyd）

 样例一：

8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3

样例一输出：

8

样例二：

4 100
10 10
15 25
20 20
30 30

样例二输出：

103

一、题目解析：

        平面上有若干个点，若点[i]可以沿着x或y增加方向移动达到点[j]，则表示可以从[i]到达[j]，否则无法到达。求：所有路径中途经已知点最多且需要添加的路径长度不大于k的。

二、解法分析：

        看一眼数据规模，能用floyd。floyd算法可以求出任意点对之间的最短路径，和题目所求方向一致（筛选一遍就可以）。面临的问题：

1、按题目规则构建图

2、能否以floyd得出的最短路径为依据得出所求

三、数据预处理

1、构建图：

        依题意，ps[i].x<=ps[j].x && ps[i].y<=ps[j].y可以表达能否到达（没有重复点）。

        依题意，符合上述条件时，ps[j].y-ps[i].y+ps[j].x-ps[i].x-1为边权。（自己画一下就知道为啥边权是-1；走不同路线时标出走向，把x增加的映射到x轴，把y增加的映射到y轴，显而易见的按规则行走任何一条[i]到[j]的最短路径长度均相等，这个描述……自己画一下就知道说的是啥了）。

2、dis[i][j]：

        floyd求出的dis[i][j]的意义是点[i]到点[j]的最短路径，1图时画的图形可知：dis[i][j]=点[i]到点[j]经过的空白格子+输入数据占据的格子数。

        故，设kij=ps[j].y-ps[i].y+ps[j].x-ps[i].x-1，有：kij-dis[i][j]为途经的已占据点个数；加上起点[i]、终点[j]即从[i]到[j]最多能经过多少输入占据的格子。

        这里有两个点需要仔细理解：

        a、dis[i][j]表达的是：从[i]到[j]的最短路径，这个路径的总长度是一定的，但是由于部分被输入数据占据了，所以：经过的空白格子越少它就越短，换言之，经过已占据的格子越多，它就越短。

        b、dis[i][j]和k的关系：若一个格子也不经过，则dis[i][j]是a中的特例：途经的都是空白的——全部由k提供。

四、floyd出马：

        分析过程往往是最耗时的，在考试时如果能用上一个“模板”将是多么幸福的事情，尤其像floyd这种短小code想敲错都难的……

        但floyd出马之前，回顾一下上面的分析，计算点[i]到点[j]的距离这个过程需要多处调用，所以function吧：

        

inline long long mathdis(int i,int j){
	//作为边的格子个数 
	return abs(ps[j].x-ps[i].x)+abs(ps[j].y-ps[i].y)-1;
}

        输入数据之后，构建好图（以下代码没有对点排序，所以必须都是1到n全运行一遍，因为无法发保证后输入的点就不能到达先输入的点）：

//构建图：能到达的构建一条边
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
				if(i==j){
					dis[i][j]=0;	
				}else{
					if(ps[i].x<=ps[j].x&&ps[i].y<=ps[j].y){
						dis[i][j]=mathdis(i,j);
					}else{
						dis[i][j]=LONG_MAX/2;
					}
				}
		}
	}

        终于轮到弗洛伊德：

//floyd
	for(int p=1;p<=n;p++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dis[i][j]=min(dis[i][j],dis[i][p]+dis[p][j]);
			}
		}
	}

        从mathdis(i,,j)-dis[i][j]中筛选出最大值即可，为了更符合刚才的思维逻辑，直接把起点[i]终点[j]加上：

//扫一遍答案 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			//构成边的空格子总数不大于k 
			if(dis[i][j]<=k){
				//mathdis包括经过的边和点（不含两端），dis仅包含经过的边 
			 	ans=max(ans,mathdis(i,j)-dis[i][j]+2);	//+2包含两端端点 
				//cout<<i<<" - "<<j<<" "<<mathdis(i,j)<<" "<<dis[i][j]<<endl;
			}
		}
	}

最后输出就行了，别忘记ans记录的是：途径点+起点+终点，题目要求的是总长度：

cout<<ans+k<<"\n";

下面就是完整代码……中缺少的定义部分：

const int MXN=505;
struct Point{
	long long x,y;
};
Point ps[MXN+1];
long long n,k,ans,dis[MXN+1][MXN+1];