链接：https://www.luogu.com.cn/problem/P1020
题意：略
题解：第一问很显然就是求一个最长的最长不上升子序列
第二问根据Dilworth定理：
最长链中元素的数目必等于其最小反链划分中反链的数目, 那么实际上就是求最长的上升子序列即为答案.
题目的输入需要一点技巧
代码：
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<string> #include<algorithm> #include<map> #include<vector> #include<set> #include<queue> #include<stack> #define Buff ios::sync_with_stdio(false) #define mem(a) memset(a, 0, sizeof a) #define read(a) scanf("%d", &a) #define readl(a) scanf("%lld", &a) #define readc(a) scanf(" %c", &a) #define reads(a) scanf("%s", a) typedef long long ll; using namespace std; const int N = 1e5 + 7; const int M = 1e6 + 7; const int INF = 1e9 + 7; const ll EF = 1e12 + 7; const ll LINF = 1e18 + 7; int dp1[N]; int dp2[N]; int a[N]; int main() { int n = 0; while(scanf("%d", &a[++n]) == 1); n--; dp1[1] = a[1]; dp2[1] = a[1]; int len = 1; for(int i = 2; i <= n; i++) { if(dp1[len] >= a[i]) dp1[++len] = a[i]; else { int l = 1, r = len; while(l < r) { int mid = (l + r) / 2; if(dp1[mid] >= a[i]) l = mid + 1; else r = mid; } dp1[l] = a[i]; } } printf("%d\n", len); len = 1; for(int i = 2; i <= n; i++) { if(dp2[len] < a[i]) dp2[++len] = a[i]; else { int l = 1, r = len; while(l < r) { int mid = (l + r) / 2; if(dp2[mid] >= a[i]) r = mid; else l = mid + 1; } dp2[l] = a[i]; } } printf("%d\n", len); return 0; }
原文：https://www.cnblogs.com/djhhxx/p/12753497.html