P1067 合唱队形
时间: 1000ms / 空间: 131072KiB / Java类名: Main
背景
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。
对于全部的数据，保证有n<=100。
题意：给你一个序列,为了使得序列满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。 需要删除一些数
问最少需要删除多少个数
题解：枚举中间点i 左边计算以i为结尾的最长上升子序列的长度l[i]
右边计算以i为起点的最长下降子序列的长度r[i] 取minx=min(minx,n-(l[i]+r[i]-1));
/******************************
code by drizzle
blog: www.cnblogs.com/hsd-/
^ ^ ^ ^
O O
******************************/
//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
#include<queue>
#include<cmath>
#define ll __int64
#define PI acos(-1.0)
#define mod 1000000007
using namespace std;
int n;
int a[];
int l[],r[];
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
int ans[];
int exm=;
ans[]=;
for(int i=;i<=n;i++)
{
if(a[i]>ans[exm])
{
exm++;
ans[exm]=a[i];
l[i]=exm;
}
else
{
int pos=lower_bound(ans+,ans+exm,a[i])-ans;
ans[pos]=a[i];
l[i]=pos;
}
}
exm=;
ans[]=;
for(int i=n;i>=;i--)
{
if(a[i]>ans[exm])
{
exm++;
ans[exm]=a[i];
r[i]=exm;
}
else
{
int pos=lower_bound(ans+,ans+exm,a[i])-ans;
ans[pos]=a[i];
r[i]=pos;
}
}
int minx=;
for(int i=;i<=n;i++)
minx=min(minx,n-(l[i]+r[i]-));
printf("%d\n",minx);
return ;
}