题目描述

友好城市

把一行城市从小到大排列之后，求另外一行的一个最大上升子序列

#include <iostream>
#include <algorithm>
using namespace std;

const int N=5010;
int a[N];
int b[N];
int f[N];
typedef pair<int,int> PII;



PII d[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        d[i]={x,y};

    }
    sort(d+1,d+n+1);

    f[1]=1;

    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<=i-1;j++)
        {
            if(d[j].second<d[i].second)
            {
                f[i]=max(f[i],f[j]+1);
            }
        }
    }

    int res=0;
    for(int i=1;i<=n;i++)
    res=max(f[i],res);

    cout<<res;





    return 0;
}

2023/11/23

直接ac
最长上升子序列的变种
要理解是如何转化的：
存成一个pair，按first排序，算second的最长上升子序列

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 5050;
int f[N];
int n;

typedef pair<int, int> pii;
pii a[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int aa, bb;
        cin>>aa>>bb;
        a[i].first = aa;
        a[i].second = bb;
    }

    sort(a+1, a+1+n);

    for(int i=1;i<=n;i++)
    {
        f[i] = 1;
        for(int j=1;j<=i;j++)
        {
            if(a[i].second > a[j].second)
            {
                f[i] = max(f[i], f[j]+1);
            }
        }
    }

    int res=0;
    for(int i=1;i<=n;i++)
    {
        res=max(res, f[i]);
    }

    cout<<res;


    return 0;
}