新疆大学ACM-ICPC程序设计竞赛五月月赛（同步赛）C勤奋的杨老师【DP/正反LIS/类似合唱队形】

链接：https://www.nowcoder.com/acm/contest/116/C

来源：牛客网

题目描述

杨老师认为他的学习能力曲线是一个拱形。勤奋的他根据时间的先后顺序罗列了一个学习清单，共有n个知识点。但是清单中的知识并不是一定要学习的，可以在不改变先后顺序的情况下有选择的进行学习，而每一个知识点都对应一个难度值。杨老师希望，后学习的知识点的难度一定不低于前一个知识点的难度（i<j时ai<=aj），而可能存在一个临界点，在临界点以后，他希望后学习的知识点的难度一定不高于前一个知识点的难度（i<j时ai>=aj）。杨老师想尽可能多的学习知识。请问：杨老师最多可以学习多少知识？

输入描述:

第一行：一个整数n（0<n<500000）接下来一行：n个整数，第i个整数ai（0<=ai<500000）表示第i道题目的难度。

输出描述:

一行一个整数，表示杨老师最多可以学习多少个知识。

示例1

输入

5

1 4 2 5 1

输出

4

【分析】：类似《合唱队形》，双向LIS，注意不严格单调（即可以相等）用upper_bound！

#include<bits/stdc++.h>

using namespace std;

const int N=500005;

int b[N],le[N],ri[N],n,ans=0x7fffffff;

void lis1(){

    int f[N],len=1;

    f[1]=b[1];

    le[1]=1;

    for(int i=2;i<=n;i++){

        if(f[len]<=b[i]) f[++len]=b[i];

        else f[upper_bound(f+1,f+len+1,b[i])-f]=b[i];

        le[i]=len;

    }

}

void lis2(){

    int f[N], len=1;

    f[1]=b[n];

    for(int i=n-1;i>=1;i--){

        if(f[len]<=b[i]) f[++len]=b[i];

        else f[upper_bound(f+1,f+len+1,b[i])-f]=b[i];

        ri[i]=len;

    }

}

int main(){

    cin>>n;

    for(int i=1;i<=n;i++) cin>>b[i];

    lis1();lis2();

    for(int i=1;i<=n;i++)

        ans=min(ans,n-le[i]-ri[i+1]);

    cout<<n-ans;

}