【題解】TIOJ 1907 . 俄羅斯娃娃

【題目敘述】https://tioj.ck.tp.edu.tw/problems/1907
【解題想法】排序,LIS

  • 每個娃娃的尺寸:寬度和高度
  • 先針對 寬度 排序(由小到大),當寬度相同時,則改由 高度 排序(由大到小)。才能滿足題意,只有當 w1 < w2 而且 h1 < h2 時,第一個娃娃才可以被放進第二個娃娃中。
  • 接著對 高度 求 LIS 長度。
  • 【例子】四個娃娃:(10, 10), (20, 30), (20, 40), (40, 50)
    • 【排序1】(10, 10), (20, 30), (20, 40), (40, 50) –> LIS 長度 = 4
    • 【排序2】(10, 10), (20, 40), (20, 30), (40, 50) –> LIS 長度 = 3
    • 依題意,(20, 30)的娃娃無法放進(20, 40)的娃娃中。【排序2】才是正確的。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(pair<int, int>x, pair<int, int>y){
    if (x.first == y.first) return x.second > y.second;
    return x.first < y.first;
}
int t, n, w, h;
vector <pair<int, int> > v;
vector <int> lis;

int main() {
    cin >> t;
    while (t--){
        cin >> n;
        v.clear();
        lis.clear();
        for (int i = 0; i < n; i++){
            cin >> w >> h;
            v.push_back({w, h});
        }
        sort(v.begin(), v.end(), cmp);
        for (auto i:v){
            if (lis.empty() || i.second > *(lis.end()-1)) lis.push_back(i.second);
            else {
                *lower_bound(lis.begin(), lis.end(), i.second) = i.second;
            }
        }
        cout << lis.size() << "\n";
    }
}
分享本文 Share with friends