[acwing面向模型编程]最长上升子序列模型

题目1：1012. 友好城市

题意：

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。

北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。

编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

输入格式
第1行，一个整数N，表示城市数。

第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

输出格式
仅一行，输出一个整数，表示政府所能批准的最多申请数。

数据范围
1≤N≤5000,
0≤xi≤10000
输入样例：
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例：
4

分析：

这个问题难在模型的转化，考虑两个直线l1 l2，只有当l2的两个坐标都大于或者小于l1的时候，两者才不会相交。所以这个题需要先对某一岸的数值排序，然后求对岸的LIS即可

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 2e6;
const int inf = 0x3f3f3f3f;
struct node
{
    int a, b;
    node(int a = 0, int b = 0) : a(a), b(b){}
}a[maxn];
int dp[maxn];

int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].a >> a[i].b;
    sort(a + 1, a + 1 + n, [](node a, node b){
        return a.a < b.a;
    });
    for(int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for(int j = 1; j < i; j++)
            if(a[j].b < a[i].b)
                dp[i] = max(dp[i], dp[j] + 1);
    }
    int maxx = 0;
    for(int i = 1; i <= n; i++)
        maxx = max(maxx, dp[i]);
    cout << maxx << endl;
}

题目2：272. 最长公共上升子序列

分析：

dp[i][j]代表在[1, i]和[1, j]中的且以j结尾的最长公共上升子序列的长度。

（引用课上的图片，侵删）
dp[i][j]就是由椭圆形的划分转移过来。
这里重点说一下优化部分。
当a[i] = a[j]的时候，我们要用k遍历[1, j - 1]找到b[k] < b[j] = a[i]的j，求max(dp[i - 1][k])，这里因为i是不变的，因此我们可以用一个变量来维护这个max.

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 3e3 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn], b[maxn];
int dp[maxn][maxn];

int main()
{
    int n; cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= n; i++)
		cin >> b[i];
	int res = 0;
	for(int i = 1; i <= n; i++)
	{
		int maxv = 0;
		for(int j = 1; j <= n; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if(a[i] == b[j]) dp[i][j] = max(dp[i][j], maxv + 1);
			if(b[j] < a[i]) maxv = max(maxv, dp[i - 1][j]);
		}
	}
	for(int i = 1; i <= n; i++) res = max(res, dp[n][i]);
	cout << res << endl;
}