题解：LG-P1020

链接
晚了，困了，写简一些。一眼瞪出最长不上升和最长上升。（dilworth定理）

如何优化LIS?

• 记录 令 \(b_k\) 表示 \(f_i=k\) 的最小 \(a_i\)，然后发现它显然是递增的，直接用 upper_bound 记录就行。
  至于如何更新 \(b\)。。。首先答案 \(t\) 一定是不超过 \(cnt+1\)，\(cnt\) 为当前总答案，如果 \(t>cnt\) 就直接更新，好办。如果 \(t\le cnt\)，前面的又比他小，所以 \(b_t:=a_i\) 是不劣的。

代码

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,a[N],b[N],c[N],ans1,ans2;
int main(){while(cin>>a[++n]);n--;for(int i=1;i<=n;i++){int t=upper_bound(b,b+ans1+1,a[i]-1)-b;ans1=max(ans1,t),b[t]=a[i];}reverse(a+1,a+n+1);for(int i=1;i<=n;i++){int t=upper_bound(c,c+ans2+1,a[i])-c;ans2=max(ans2,t),c[t]=a[i];}cout<<ans2<<'\n'<<ans1;return 0;
}

• 晚安。