合唱队形
题目描述
N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
输入格式
输入的第一行是一个整数N(2<=N<=100),表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
输出格式
输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。
样例输入
8
186 186 150 200160 130 197 220
样例输出
4
题目评测链接:http://www.rqnoj.cn/Problem_26.html
同类题目扩展:http://blog.csdn.net/yuyanggo/article/details/8594315
http://blog.csdn.net/yuyanggo/article/details/8600067
解析:读懂题后,可以知道这道题实际上是要求以i点为最后一个点的最长上升子序列,需要删除的点个数(记为lz[i]),与以i点为起点的最长下降子序列,需要删除的点个数(记为ly[i])。那么我们就可以枚举中点i,然后用求最长子序列长度的方法(方法链接)分别求出lz[i]与ly[i],结果就为ans=min(ans,lz[i]+ly[i]).
代码见:
动态规划+单调队列
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int T[110],lz[110],ly[110],q[110],n,len; void init() { freopen("hechang.in","r",stdin); freopen("hechang.out","w",stdout); } int find(int x) { int l=1,r=len,mid; while(l<=r) { mid=(l+r)>>1; if(x>q[mid]) l=mid+1; else r=mid-1; } return l; } void work() { scanf("%d",&n); int i; for(i=1;i<=n;i++)scanf("%d",&T[i]); q[1]=T[1]; len=1; lz[1]=0; //预处理lz[i] for(i=2;i<=n;i++) { if(T[i]>q[len])q[++len]=T[i]; else if(T[i]<q[len])q[find(T[i])]=T[i]; lz[i]=i-len;//此时的len表示以i为终点,最长上升子序列长度 } q[1]=T[n]; len=1; ly[n]=0;//预处理ly[i],在处理ly[i]时,从n开始逆序枚举,就可以 for(i=n-1;i>=1;i--) 转变为与处理lz[i]的相同之问题 { if(T[i]>q[len])q[++len]=T[i]; else if(T[i]<q[len])q[find(T[i])]=T[i]; ly[i]=n-i+1-len; } int ans=100000; for(i=1;i<=n;i++)ans=min(ans,lz[i]+ly[i]); printf("%d\n",ans); } int main() { init(); work(); //while(1); return 0; }