本文主要是介绍POJ 3636 Nested Dolls -（最长上升子序列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3636
最小链划分数 = 最长反链长度
按如下关系排序：
w 1 > w 2 ∨ ( w 1 = w 2 ∧ h 1 ≤ h 2 ) w_1 \gt w_2 \lor (w_1 = w_2 \land h_1 \le h_2) w1>w2∨(w1=w2∧h1≤h2)
定义反链：
w 1 ≥ w 2 ∧ h 1 ≤ h 2 w_1 \ge w_2 \land h1 \le h_2 w1≥w2∧h1≤h2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;inline int read_int() { int a; scanf("%d", &a); return a; }
inline void outdn(int x) { printf("%d\n", x); }struct doll_t {int w, h;
};struct comp_t {bool operator()(doll_t d1, doll_t d2) const {if (d1.w > d2.w) return true;if (d1.w < d2.w) return false;return d1.h < d2.h;}
};int main() {int T = read_int();comp_t comp;while (T--) {const int m = read_int();vector<doll_t> dolls(m);for (int i = 0; i < m; i++) {dolls[i].w = read_int();dolls[i].h = read_int();}sort(dolls.begin(), dolls.end(), comp);vector<int> seq(m, 0x7fffffff);for (int i = 0; i < m; i++)*upper_bound(seq.begin(), seq.end(), dolls[i].h) = dolls[i].h;outdn(lower_bound(seq.begin(), seq.end(), 0x7fffffff) - seq.begin());}//system("pause");return 0;
}
这篇关于POJ 3636 Nested Dolls -（最长上升子序列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
