合唱队形 解题报告(LIS)

思路很简单，就是枚举最高点，然后两边分别lis再求len1+len2+1的最大值，主要是lis的nlogn写法。

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
const int maxn=105;
int n,t[maxn];
int cal(int m){
    int b1[maxn]={0};
    int len1=0;
    rep(i,1,m-1){
        if(t[i]>=t[m]) continue;
        if(t[i]>b1[len1]){
            b1[++len1]=t[i];
        }
        else{
            int pos=lower_bound(b1+1,b1+len1+1,t[i])-b1;
            b1[pos]=t[i];
        }
    }
    int b2[maxn]={0},len2=0;
    per(i,m+1,n){
        if(t[i]>=t[m]) continue;
        if(t[i]>b2[len2]){
            b2[++len2]=t[i];
        }
        else{
            int pos=lower_bound(b2+1,b2+1+len2,t[i])-b2;
            b2[pos]=t[i];
        }
    }
    return len1+len2+1;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    read(n);rep(i,1,n) read(t[i]);
    if(n==2){
        write(0);
        return 0;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,cal(i));
    }
    write(n-ans);
    //===========================================================
    return 0;
}