TYVJ P1067 合唱队形 Label:上升子序列？

背景

NOIP2004 提高组 第三道

描述

    N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

    合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，  则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

    你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入格式

   输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

输出格式

    输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

测试样例1

输入

8 
186 186 150 200 160 130 197 220

输出

4

备注

对于50％的数据，保证有n<=20；
对于全部的数据，保证有n<=100。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1<<30
using namespace std;
int N,res=INF,a[105],b[105],dp[105],f[105],l,r;
int longest(int k){
    fill(dp,dp+N,INF);
    for(int i=1;i<=k;i++){
        *lower_bound(dp,dp+N,a[i])=a[i];
        if(i==k) l=lower_bound(dp,dp+N,INF)-dp;
    }
//    printf("k=%d l=%d ",k,l);
    fill(dp,dp+N,INF);
    for(int i=1;i<=N-k+1;i++){
        *lower_bound(dp,dp+N,b[i])=b[i];
        if(i==N-k+1) r=lower_bound(dp,dp+N,INF)-dp;
    }
//    printf("r=%d\n",r);
    if(r==1||l==1) return -1;
    return l+r-1;
}
int main(){
//    freopen("01.txt","r",stdin);
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    for(int i=1;i<=N;i++) b[i]=a[N-i+1];
//    for(int i=1;i<=N;i++) printf("%d ",b[i]);
    
    for(int i=1;i<=N;i++){
        int k=longest(i);
        if(k==-1) k=INF;
        else k=N-k;
        res=min(res,k);
    }
    
    if(res==INF) res=0;
    printf("%d\n",res);
    return 0;
}

直接顺序读入a数组，再逆序复制一份到b，枚举中间点，过一下最长上升子序列，

记录当中间点推入时的序列长度，得到最小值；

其实可以不用逆序复制，为了不浪费时间，采用了O(nlogn)的lower_bound;

看了下题解发现本来就是上升或下降（即没有答案时）要输出0

非二分做法如下

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
int a[10005],zuo[10005],you[10005],N;
int zuo_(){
    fill(zuo,zuo+10000,1);
    for(int i=1;i<=N;i++){
        for(int j=i+1;j<=N;j++){
            if(a[j]>a[i]) zuo[j]=max(zuo[j],zuo[i]+1);
        }
    }
}
int you_(){
    fill(you,you+10000,1);
    for(int i=N;i>=1;i--){
        for(int j=i-1;j>=1;j--){
            if(a[j]>a[i]) you[j]=max(you[j],you[i]+1);
        }
    }
}
int main(){
    freopen("01.txt","r",stdin);
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d",&a[i]);
    
    zuo_();
    you_();
    int ans=0;

    
    for(int i=1;i<=N;i++)
        ans=max(ans,zuo[i]+you[i]-1);
    if(ans==1) puts("0");
    else printf("%d\n",N-ans);
    return 0;
}