[线性dp] aw1012. 友好城市(最长上升子序列模型+思维)

文章目录

• • 0. 前言
  • 1. LIS 变种+思维抽象

0. 前言

相关：

[线性dp] 最长上升子序列(模板题+最长上升子序列模型)

1. LIS 变种+思维抽象

1012. 友好城市

本题很考思维抽象。

重点： 线性

dp

、LIS 问题、思维抽象

思路：

• 题目保证河的南北两岸城市能够一一对应起来，成为一个友好城市
• 那么当我们按照南岸城市坐标从小到大在数轴上排好序，北岸的城市不需要进行移动
• 顺序从小到大枚举排序一岸，并找其对应的友好城市。能够发现城市间如果航道交叉，那么意味着构成一个 叉 的形状，由于排序一岸是从小到大枚举的，所以当未排序一岸出现编号互逆的情况，就出现了交叉情况
• 可以发现，任何一种合法的航道组合方式，都是一种子序列
• 那么问题抽象为：排序一岸后，寻找对岸的最长上升子序列问题数量，即为答案

这问题的关键，就是如何想到排序的呢？

• 由于两者有唯一确定的位置关系，排序后能确定一边单调性，选中后的对应边要有序，不能随便逆序
• 多试
• 经验

排序后LIS代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5005;

int n;
PII q[N];
int f[N];

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