acwing 1012 友好城市

简介: acwing 1012 友好城市

活动 - AcWing

线性dp,dp实现很简单,主要是怎么能想到用dp,怎么样才能用dp;当我们把南岸城市从小到大排序,然后再找最长不上升子序列

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 50100 ;
typedef pair<int,int> PII ;
PII a[N] ; 
int dp[N] ;
int n ; 
int main(){
  cin >> n ;
  for(int i = 1 ; i <= n ; i ++) cin >> a[i].first >> a[i].second;
  sort(a+1,a+n+1) ;
  for(int i = 1 ; i <= n ; i++){
    dp[i] = 1 ;
    for(int j = 1 ; j <= i ; j ++){
      if(a[j].second < a[i].second) dp[i] = max(dp[i],dp[j] + 1 );
    }
  }
  int res = 0 ;
  for(int i = 1 ; i <= n ; i ++ ) res = max(dp[i],res) ;
  cout << res << endl ; 
  
}
目录
相关文章
|
2月前
acwing 1010 拦截导弹
acwing 1010 拦截导弹
36 1
AcWing 1265. 数星星(每日一题)
AcWing 1265. 数星星(每日一题)
|
2月前
acwing 898 数字三角形
acwing 898 数字三角形
33 2
|
2月前
acwing 188 武士风度的牛
acwing 188 武士风度的牛
12 0
|
2月前
acwing 1116 马走日
acwing 1116 马走日
15 0
|
2月前
acwing 1107 魔板
acwing 1107 魔板
14 0
|
2月前
acwing 285. 没有上司的舞会
acwing 285. 没有上司的舞会
20 0
|
2月前
acwing 1014 登山
acwing 1014 登山
32 0
|
2月前
acwing 1017 怪盗基德的滑翔翼
acwing 1017 怪盗基德的滑翔翼
35 0
AcWing 562. 壁画(每日一题)
AcWing 562. 壁画(每日一题)