合唱队形
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...
Ti+1>…>TK(1<=i<=K)。
【任务】已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
【输入】
输入的第一行是一个整数N(2<=N<=100)，
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示同学的总数。 第二有N个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
【输出】
输出最少需要几位同学出列。
【样例输入】
8
186 186 150 200 160 130 197 220
【样例输出】
4
【数据结构】
数组a[i]是第i个人的身高
b[i]是从左边第一个到a[i]的最长上升子序列
c[i]是从右边第一个到a[i]的最长上升子序列
【递推关系式】
b[i]=max{b[j](1<=j a[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
using namespace std;
#define MAXN 200
void print_array();
int N,a[MAXN], b[MAXN], c[MAXN]; void main()
{int i, 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] < a[i] && b[j] + 1 > 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] < a[i] && c[j] + 1 > 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<<"出列人数:"<
本文档为【合唱队形】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483