2126: 信息学奥赛一本通T1263-友好城市 最长不下降子序列

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义结构体f，包含两个整数成员xi和yi
struct f{
    int xi, yi;
} a[10005]; // 声明一个结构体数组a，大小为10005
int n, dp[10005]; // 声明变量n和动态规划数组dp，大小为10005
// 比较函数，用于排序
bool cmp(f a, f b){
    return a.xi < b.xi; // 按照xi的值进行升序排序
}
int main(){
    cin >> n; // 输入n的值
    for(int i = 1; i <= n; i++){
        cin >> a[i].xi >> a[i].yi; // 输入每个结构体的xi和yi值
        dp[i] = 1; // 初始化dp数组的值为1
    }
    sort(a + 1, a + n + 1, cmp); // 对一侧进行排序
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(a[i].yi > a[j].yi){// 求出另一侧最长不下降子序列即可
                dp[i] = max(dp[i], dp[j] + 1); // 更新dp数组的值
            }
        }
    }
    cout << *max_element(dp + 1, dp + n + 1) << endl; // 输出dp数组中的最大值
    return 0;
}