信息学奥赛一本通 2089：【22CSPJ普及组】上升点列(point) | 洛谷 P8816 [CSP-J 2022] 上升点列

【题目链接】

ybt 2089：【22CSPJ普及组】上升点列(point)
洛谷 P8816 [CSP-J 2022] 上升点列

【题目考点】

1. 动态规划

2. 曼哈顿距离

平面直角坐标系中两个整数点之间的绝对轴距总和。
点$p_1(x_1,y_1)$和点$p_2(x_2,y_2)$的曼哈顿距离为
$dis(p_1,p_2)=|x_1-x_2|+|y_1-y_2|$

【解题思路】

给定n个点，添加k个点，看能形成上升点序列的最大长度。
上升点序列：相邻两点间的曼哈顿距离为1，且横纵坐标值单调不减的点序列。
点的数量可以变化，添加的点的数量可以变化，因此考虑将这两个量设为阶段。

状态定义

• 阶段：已有前i个点，添加j个点
• 决策：将可以添加的点添加到哪个位置
• 策略：添加点后得到点序列的方案
• 策略集合：
  直接考虑，应该是已有前i个点，再添加j个点得到的所有上升点序列。
  考虑到应该让每个已有点参与到构成点序列的过程中，这样才能考虑到所有可能的上升点序列方案。因此这里再加一层限定，就是第i点必须参与到上升点序列中。
  因此策略集合为：已有前i个点，再添加j个点构成的包含第i点的所有上升点序列。
• 条件：上升点序列长度最大
• 统计量：序列长度

状态定义：$dp[i][j]$：已有的前i个点中添加j个点所构成的所有包含第i点的上升点序列的最大长度。
初始状态：第i点在添加j个点后，至少能得到一个长度为j+1的上升点序列。因此有初始状态$dp[i][j]=j+1$

状态转移方程

• 策略集合：已有前i个点，再添加j个点构成的包含第i点的所有上升点序列
• 分割策略集合：根据上升点序列中第i点的前一个已有点分割策略集合。

设第$i$点前的第一个已有点为第$h$点，$h$最小可以选择第1号点，最大时可以是第$i-1$点，因此$1\le h<i$。
那么在上升点序列中从第$h$点到第$i$点之间就没有已有点了，全部都是新添加的点。生成的点序列中第$h$点到第$i$点的情况为：
第$h$点，添加点1，添加点2，…，添加点x，第$i$点。

已有点中是第i点的坐标为$(x_i,y_i)$
如果要在第h点和第i点两点之间添加点使其形成一个上升点序列，需要添加的点的数量为第h点和第i点两点之间的曼哈顿距离减1，即$dis(h,i)-1=|x_h-x_i|+|y_h-y_i|-1$（其中$dis(h,i)$是第h点和第i点两点之间的曼哈顿距离）

能将第h点和第i点连起来形成一个上升点序列至少需要$dis(h,i)-1$个点，现在有$j$个可添加点，因此必须满足$j\ge dis(h,i)-1$，才可以形成一个上升点序列。
同时，由于上升点序列要求横纵坐标单调不减，第h点$(x_h,y_h)$在第i点$(x_i,y_i)$点前，一定要满足$x_h\le x_i$与$y_h\le y_i$。
可以预先将所有已有点按照x从小到大、x相等时y从小到大进行排序。这样排序后可以保证上升点序列中第i点的下一个点，一定在排序后的已有点序列第i点的后面。（因为从第i点到第i点前面的点，一定是横坐标减少或纵坐标减少）。
如果满足以上条件，则可以选择第h点作为第i点前的第一个已有点，两点之间添加$dis(h,i)-1$个新的点，形成上升点序列。

已有的前$i$个点中添加$j$个点所构成的所有包含第$i$点的上升点序列的最大长度$dp[i][j]$，是已有前h个点，添加$j-(dis(h,i)-1)$个点构成的包含第$h$点的最长的上升点序列的长度，加上从第h点到第i点不包含第h点的点的数量，也就是第h点到第i点的曼哈顿距离$dis(h,i)$。
接下来对于$1\le h<i$的所有情况，求$dp[i][j]$的最大值。

状态转移方程： d p [ i ] [ j ] = m a x { d p [ h ] [ j − d i s ( h , i ) + 1 ] + d i s ( h , i ) } , 1 ≤ h < i dp[i][j] = max\{dp[h][j-dis(h,i)+1]+dis(h,i)\}, 1\le h < i dp[i][j]=max{dp[h][j−dis(h,i)+1]+dis(h,i)},1≤h<i

最终得到的最长的上升点序列可能以任何一个已有点为结尾，因此结果为$dp[1][k]\sim dp[n][k]$中的最大值

【题解代码】

解法1：动态规划

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 505
#define K 105
using namespace std;
struct Point
{
	int x, y;
} p[N];
bool cmp(Point a, Point b)
{
	return a.x < b.x || a.x == b.x && a.y < b.y;
}
int dis(int i, int j)//p[i]到p[j]的曼哈顿距离 
{
	return abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
}
int dp[N][K], ans;//已有的前i个点中添加j个点所构成的所有包含第i点的上升点序列的最大长度。
int main()
{
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; ++i)
		cin >> p[i].x >> p[i].y;
	sort(p+1, p+n+1, cmp);
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 0; j <= k; ++j)
		{
			dp[i][j] = j+1;
			for(int h = 1; h < i; ++h) 
				if(j >= dis(h, i)-1 && p[h].x <= p[i].x && p[h].y <= p[i].y) 
					dp[i][j] = max(dp[i][j], dp[h][j-dis(h, i)+1]+dis(h, i));
		}
		ans = max(ans, dp[i][k]);
	}
	cout << ans;
	return 0;
}