POJ 3636 Nested Dolls -（最长上升子序列）

本文主要是介绍POJ 3636 Nested Dolls -（最长上升子序列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://poj.org/problem?id=3636
最小链划分数 = 最长反链长度
按如下关系排序：
$$w_1>w_2\vee (w_1=w_2\wedge h_1\le h_2)$$
定义反链：
$$w_1\ge w_2\wedge h1\le h_2$$

#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 -（最长上升子序列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---