1012. 友好城市(lis,轉化模型)

由于每個城市都有且僅有一個友好城市，而且每個城市的友好城市還互不相同

等價于：有 2k個城市 ，那麼就有 k 對 友好城市

如果發生航線相交，就會有如圖的情況，x2>x1,y2<y1

那麼要想保證所有友好城市的航線不會相交，就是要讓一對城市的y，x均是一個最長上升子序列

(y不一定大于x，簡單可證這不成立，隻需要保證所有選出的城市他們的y和x都是最長上升子序列就行了)

1.那麼我們先對x排序，這樣子的話，所有選出的城市的x都預設是上升子序列

2.再從城市的y中尋找一個最長上升子序列

總結：1.排序解決雙關鍵字問題

           2.畫圖，轉換模型

#include <iostream>
#include <algorithm>

using namespace std;
const int N=5000+10;
typedef pair<int,int> PII;
PII a[N];
int dp[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i].first>>a[i].second;
    sort(a,a+n);
    int res=0;
    for(int i=0;i<n;i++)
    {
        dp[i]=1;
        for(int j=0;j<i;j++)
            if(a[j].second<a[i].second)
                dp[i]=max(dp[j]+1,dp[i]);
        res=max(res,dp[i]);
    }
    cout<<res;
}