40人漂亮简单的合唱队形

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

位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，

K，他们的身高分别为T1，T2，…，TK，则他们的身高满足

T1<...Ti+1>…>TK(1<=i<=K)。

【任务】已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩

下的同学排成合唱队形。

【输入】

输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。

第二有N个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身

高(厘米)。

【输出】

输出最少需要几位同学出列。

【样例输入】

8

0

【样例输出】

4

【数据结构】

数组a[i]是第i个人的身高

b[i]是从左边第一个到a[i]的最长上升子序列

c[i]是从右边第一个到a[i]的最长上升子序列

【递推关系式】

b[i]=max{b[j](1<=ja[j]}+1

符合合唱队的队列是b[i]+c[i]-1(a[i]被重复计算了一次)，

而题目要求的合唱队列是：max{b[i]+c[i]-1}1<=i<=总人数

要挑出去的人数即：总人数-max{b[i]+c[i]-1}

#include

#include

usingnamespacestd;

#defineMAXN200

voidprint_array();

intN,a[MAXN],b[MAXN],c[MAXN];

voidmain()

{inti,j,max;

do{cin>>N;

}while(N>=MAXN);

for(i=1;i<=N;i++)

cin>>a[i];

memset(b,0,sizeof(a));

memset(c,0,sizeof(c));

/*左侧的最长上升子序列*/

b[1]=1;

for(i=2;i<=N;i++)

{max=0;

for(j=i-1;j>=1;j--)

{if(a[j]max)

max=b[j];

}

b[i]=max+1;

}

/*求左侧的最长上升子序列*/

c[N]=1;

for(i=N-1;i>0;i--)

{max=0;

for(j=i+1;j<=N;j++)

{if(a[j]max)

max=c[j];

}

c[i]=max+1;

}

/*枚举求最长队形*/

max=b[1]+c[1];

for(i=2;i<=N;i++)

{if(b[i]+c[i]>max)

max=b[i]+c[i];

}

cout<<"出列人数:"<

print_array();//输出数组a、b、c

}

voidprint_array()

{inti;

cout<<"i:";

for(i=1;i<=N;i++)

cout<

cout<

printf("a[i]:");

for(i=1;i<=N;i++)

cout<

cout<

cout<<"b[i]";

for(i=1;i<=N;i++)

cout<

cout<

cout<<"c[i]";

for(i=1;i<=N;i++)

cout<

cout<

}