题目传送门 https://www.luogu.com.cn/problem/P1020
解题思路:
其实就是求一遍最长不上升子序列和最长上升子序列
AC 代码:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- int n,a[100001],f[100001],dp[100001],len = 1,tot = 1,p;
- int main() {
- while(scanf("%d",&a[++p]) != EOF);
- f[1] = a[1];
- dp[1] = a[1];
- p--;
- for(int i = 2;i <= p; i++) {
- if(a[i] <= f[len])
- f[++len] = a[i];
- else {
- int u = upper_bound(f+1,f+len+1,a[i],greater<int>()) - f;
- f[u] = a[i];
- }
- if(a[i]> dp[tot])
- dp[++tot] = a[i];
- else {
- int o = lower_bound(dp+1,dp+tot+1,a[i]) - dp;
- dp[o] = a[i];
- }
- }
- printf("%d\n%d",len,tot);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3325832.html