偏序集、哈斯图、Dilworth

偏序

偏序关系满足：自反性、反对称性和传递性
便于理解引入哈斯图

哈斯图

对于元素 x，如果 x<y 且不存在 z 使得 x<z<y，那么 y 就是 x 的覆盖元素，在哈斯图中连出一条 x−>y 的有向边。通过覆盖关系生成的图就是哈斯图。
偏序关系可以理解为：自环、不存在回路

Dilworth

对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真。

设 C 是偏序集的一个子集，如果 C 中元素互相可比，那么称 C 是链；如果 C 中元素互相不可比，则称 C 是反链。

反链元素个数最多是 2 ，整个图至少需要 2 条链 ( {1,2,4,8} 和 {3,6,12} ) 来覆盖。

显然反链中任意两个元素不可比，若要求最小链划分数还需每一条链不存在反链中任意两个及以上元素，故最小链划分数此时大于等于最大反链长度，若大于时多余的链中的每一个元素必然和之前的链中元素存在一条简单路径（因为最大反链保证了这个元素必然和反链中至少一个元素存在偏序关系），此时存在一条链可以合并这个元素。

所以最小链划分数=最大反链长度。

最少的不上升子序列与最长上升子序列

最少的不上升子序列的个数 = 最长上升子序列的长度

显然不上升子序列与上升子序列不存在偏序关系

最少的不上升子序列的个数 类比成 最小链划分数
最长长生子序列的长度 类比成 最大反链长度

P1020

题目链接

1. 求不上升子序列的最大长度
2. 求至少需要几个导弹才能拦截

核心：找到一个和不上升子序列不存在偏序关系的关系

最小(不上升子序列)个数 = 最小(链)划分数 = 最大反链长度 = 最大上升子序列长度

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define all(a) a.begin(),a.end()
using namespace std;
using ll = long long;
template<typename T>
ostream& operator << (ostream& out, vector<T> ve) {cout << "(";for(int i = 0; i < ve.size(); i++) {cout << ve[i] << ",)"[i == ve.size() - 1];}return out;
}
void solve(){string s;getline(cin, s);stringstream ss(s);vector<int>a;int x;while(ss >> x) {a.push_back(x);}// 最长不上升子序列长度reverse(all(a));vector<int>ve;for(auto &t:a) {auto p = upper_bound(all(ve), t);if(p == ve.end()) ve.push_back(t);else *p = t;}cout << ve.size() << "\n";reverse(all(a));ve.clear();for(auto &t:a) {auto p = lower_bound(all(ve), t);if(p == ve.end()) ve.push_back(t);else *p = t;}cout << ve.size() << "\n";
}int main() {ios::sync_with_stdio(false);int t=1;//cin >> t;while(t--){solve();}
}