[題解]APCS飛黃騰達

110/01 實作題第四題 飛黃騰達

這是一題我在考試中根本沒有碰的題目（能力不足），聽到別人是說這是一題經典的LIS，所以寒假就開始了解動態規劃的題目。這一題關鍵是先把x座標排列好（可以想成是LIS中的數列順序），然後依照y座標做LIS。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define int long long
using namespace std;
int n;

signed main(){
    ios;
    cin>>n;
    pair<int, int> P[n];
    for(int i=0;i<n;i++){
        int x,y;cin>>x>>y;
        P[i] = make_pair(x, y);
    }
    sort(P, P+n);//利用pair排序，會先依照x排序，如果x相同，則照y排序
    vector<int>ans;//儲存LIS
    ans.push_back(P[0].second);
    for(int i=1;i<n;i++){
        int now = P[i].second;
        if(now>=ans.back())ans.push_back(now);
        else{
            int ind = upper_bound(ans.begin(),ans.end(),now)-ans.begin();
            ans[ind] = now;
        }
    }
    cout<<ans.size()<<endl;
}

這裡有一點跟LIS不一樣，它不需要嚴格遞增，因此在第20使用 >= ，還有第22行使用upper_bound也是因為不需要嚴格遞增（如果要插入的值在LIS裡面就已經有了，兩者都可以保留，所以用upper_bound，取第一個大於它的數值更改掉。

---