【hihocoder】 1718 最长一次上升子序列

地址

https://hihocoder.com/problemset/problem/1718

题目

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个由N个元素组成的序列： A1, A2, ... AN，请你找出其中最长的子序列B1, B2, ... BM满足其中至多有一次上升，即只有一次Bi+1 - Bi > 0。

输入
第一行包含一个整数N。
第二行包含N个两辆不同的整数，A1, A2, ... AN。
对于30%的数据，1 <= N <= 1000
对于100%的数据，1 <= N <= 100000 , 1 <= Ai <= 100000

输出
最长的满足条件的序列的长度

样例输入
5
3 5 4 1 2
样例输出
4

思路

从前往后求一遍最长下降子序列，然后倒着求一遍最长上升子序列，对于每个位置只需要记录两个子序列的最大长度，然后枚举拼接位置，最大长度等于这个位置的最长下降子序列加最长最长上升子序列长度
我代码用的是个玄学做法，就不讲了。

代码

#include <bits/stdc++.h>

using namespace std;

#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
const double pi=acos(-1.0);
const int K=1e5+7;
const int mod=1e9+7;

int dp[K],sp[K];

int main(void)
{
    int n,ca=1,cb=1;
    cin>>n;
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        if(i==1)
        {
            dp[1]=sp[1]=-x;
            continue;
        }
        x=-x;
        if(sp[cb]<=x)
            sp[++cb]=x;
        else
            sp[upper_bound(sp+1,sp+1+cb,x)-sp]=x;
        if(dp[ca]>x)
        {
            cb=max(cb,ca+1);
            for(int j=ca+1;j>=1;j--)
            if(sp[j]>x)
                sp[j]=x;
            else
                break;
        }
        if(dp[ca]<=x)
            dp[++ca]=x;
        else
            dp[upper_bound(dp+1,dp+1+ca,x)-dp]=x;
    }
    printf("%d\n",max(ca,cb));
    return 0;
}