题意：求出一个最长单调不增子序列和最少的个数的单调不加的子序列的个数。
根据dilworth:最少的全集个数等于最大的反链的元素个数。
可以将求最少的个数的单调不加的子序列的个数转化为求最长上升子序列的长度。
于是用二分+贪心来写
点击查看代码
#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>
#include <string.h>
#include <map>
#include <queue>
#include <list>
#include <cmath>
#include <iomanip>
#define int long long
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc u<<1
#define rc u<<1|1
#define gcd __gcd
#define double long double
#define endl "\n"
#define INF LLONG_MAX
#define mod 1000000007
#define N 100005
const double PI = 3.14159265358979323846;
using namespace std;
int a[N], b[N], c[N], n, len1, len2, x;
signed main()
{
ios;
while (cin >> x)a[n++] = x;
b[0] = a[0]; c[0] = a[0];
for (int i = 1; i < n; i++)
{
if (b[len1] >= a[i])b[++len1] = a[i];
else
{
int index = upper_bound(b , b + len1+1, a[i], greater<int>()) - b;
b[index] = a[i];
}
if (a[i] > c[len2])c[++len2] = a[i];
else
{
int index = lower_bound(c,c + len2+1, a[i]) - c;
c[index] = a[i];
}
}
cout << len1 + 1 << endl << len2 + 1 << endl;
return 0;
}