The longest ascending subsequence model acwing 1012 Sister cities

Longest ascending subsequence model AcWing 1012. Friendly city

Original link

AcWing 1012. Friendly city

Algorithm tags

DP linear DP Longest ascending subsequence

Ideas

Sort friendly cities at one end , The longest ascending sequence at the other end is the answer

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 5005, INF = 0x3f3f3f3f;
int f[N], f1[N], a[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
struct Node{
    int a,b;
}node[N];
bool cmp(Node A, Node B){
    return A.b<B.b; 
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n=read(),ans=0;
	rep(i, 0, n){
	    node[i].a=read(),node[i].b=read(); 
	}
	sort(node, node+n, cmp);
	rep(i, 0, n){
	    f[i]=1;
	    rep(j, 0, i){
	        if(node[j].a<node[i].a){
	            f[i]=max(f[i], f[j]+1);
	        }
	    }
	    ans=max(ans, f[i]);
	}
	printf("%lld\n", ans);
}

y Master code

#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

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

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &city[i].first, &city[i].second);
    sort(city, city + n);

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

    printf("%d\n", res);

    return 0;
}

tips

Double keyword sorting , Use pair, There is no need to create a new structure . Consistent running time

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support