题目描述
求出最长插入k个点的最长满足条件(后面的那个点满足要么x+1,要么y+1)的子序列。
样例
输入样例
8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3
输出样例
8
最长上升子序列变形
含义:f[i][j]指的是以第i个点为结尾,插入j个点的情况下最长的满足条件的子序列长度
状态转移方程:从j点到i的时候的最长的满足条件子序列长度
$f[i][p] = max(f[i][p],f[j][p-(dist(j,i)-1)] + dist(j,i) + 1)$
初始化:以第i个点为结尾,前面插入j个点的至少的最长的满足条件序列大小是 $j+1$
blablabla
时间复杂度
$O(k*n^2)$
C++ 代码
#include<bits/stdc++.h>
// f[i][j] 指的是 前i个点插入j个点的最大长度
// 类似于最长上升子序列,可以用n^n的复杂度计算
#define x first
#define y second
using namespace std;
const int N = 510;
int n, k, dp[N][N];
pair<int,int> a[N];
int main()
{
cin >> n >> k;
for(int i = 1;i <= n ;i ++) cin >> a[i].x >> a[i].y;
sort(a + 1, a + 1 + n);
for(int i = 1; i <=n ;i ++)
for(int j = 0; j <=k;j ++)
dp[i][j] = j + 1; // 在i点前面插入j个点的初始最大序列长度至少有j+1
// 模仿最大上升子序列的写法k*n^2
for(int i = 2;i <= n;i ++){
// 找到前面的不大于当前数的数进行状态转移
for(int j = i - 1; j; j--) // 这题是二维的坐标,所以 这里保证了x不超过a[i].x
{
if (a[j].y > a[i].y) continue; // 这里保证了y不超过a[i].y
// 计算曼哈顿距离-1
int dis = a[i].x - a[j].x + a[i].y - a[j].y - 1;
// 这里就是
for(int p = dis; p <= k; p++) dp[i][p] = max(dp[i][p],dp[j][p-dis] + dis + 1); //插入的dist点加上原本那个点就得加上1
}
}
int res = 0;
for(int i = 1; i <= n; i ++) res = max(res, dp[i][k]);
cout << res << endl;
return 0;
}
for(int i = 1; i <=n ;i ) //此处选择终点
for(int j = 0; j <=k;j ) // 选择与终点连接的前一个点
//计算曼哈顿距离尝试连接两个点, 到此为止与弗洛伊德算法的区别并不是非常大,都是选择一个终点一个中继点不断更新,计算最短距离
int dis = a[i].x - a[j].x + a[i].y - a[j].y - 1;
// 区别在这里,这里记录了一个值dp[i][j],我们需要注意,此处只有终点而没有起点,这样是处理不了最短路径的问题,于是引入一个新的参数k,体力值,这样实际上,我们可以通过这个数值去寻找某一条路线的起点(从终点做阶梯线段)。于是起点的缺失被k解决了。这也是为何这样子动态规划时间复杂度是o(N^2*k),我们将k换为起点,就会变成n,于是就成为了O(N^3),这样子就等价于弗洛伊德算法的时间复杂度了。
//尝试使用不同的体力值(等价于使用不同的起点)去连接这两个点
for(int p = dis; p <= k; p++) dp[i][p] = max(dp[i][p],dp[j][p-dis] + dis + 1);
与弗洛伊德算法比较
for(int k=1;k<=n;k)
for(int i=1;i<=n;i)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
其中i,j分别代表起点、终点。而k代表他们之间的中继点。
使用曼哈顿距离事实上是因为题目规定了欧几里得距离恰好为 1。实际上这需要以起点为圆心做半径为1的圆,又由于题目中仅仅考虑整数点,故而只有4个点,又有横坐标、纵坐标值均单调不减,这意味着只需要考虑两个点。
由此我们考虑将整个数据作为一个一个坐标系的方块,如(1,1)代表坐标上的第一个方块,(2,2)代表它斜上方的方块。又由于只能向右或者向上,则考虑为走迷宫的问题。即如何走才能使得整体的面积最大。体力为k,每走到一个已知方块就可以恢复一点体力。直至走完为止。
事实上这只需要求每两个点之间的最小距离(即从a到b怎么走体力花费最少),这样可以使尽可能多的方块连接。只需要使用弗洛伊德计算每个点之间的距离 o(n3)【当k很大,而n很小时会更好】。
或者我们使用dfs,由于这是一个走路的问题,对于每个点要么走到它右方的点,要么走到它上方的点,要么走到它右上方的点,由此做dfs,找到最长的路径。
使用动态规划一定程度上和弗洛伊德算法计算两点的最小距离有共同之处,弗洛伊德通过不断更新两点的最小距离,找出所有的两点距离。动态规划的max(dp[i][p],dp[j][p-dis] + dis + 1);也是在更新距离。