【題目敘述】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";
}
}