6698人阅读
算法（14）
& & &N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。&& 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，& 则他们的身高满足T1&...&Ti&Ti+1&…&TK(1&=i&=K)。&& 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。&
&&&&&输入格式 Input Format&&&&& 输入的第一行是一个整数N(2&=N&=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130&=Ti&=230)是第i位同学的身高(厘米)。&
&&&&&输出格式 Output Format&&&&& 输出包括得到的最优队列的同学个数 以及最终同学的身高排列
& & &这个问题可以分解为 对于0&=i&=n-1(n为同学数) 我们要求得满足子序列[0, i)的升序排列最优个数p加上子序列[i, n)满足降序最优个数q即p+q最大的i值 对于升序和降序的最优解 可以用动态规划来构造
& & &数组a[i]是第i个人的身高，b[i]是从左边第一个到a[i]的最长上升子序列，c[i]是从右边第一个到a[i]的最长上升子序列。这题的关键在于理解如何获得b[i]和c[i]的值。我们可以知道，不管a[i]为什么值时，b[i]&=1;（因为它本身就是一个上升序列元素。）假设 i=1 ，此时b[1]=1;因为a[1]的前面没有元素。那么如果a[2]&a[1]，显然可以得到b[2]=b[1]+1;
因为a[1]，a[2]是一个上升子序列。如果a[3]&=a[2]且a[3]&=a[1]，那么b[2]为2；因为它可以和a[1]组成上升子序列。同理，若a[3]&a[1]..a[3-1]，则b[3]=max{b[1]...b[3-1]}。由此我们可以得到递推关系式： b[i]=max{b[j](1&=j&i)|a[i]& a[j]}+1 （学过集合的应该看得懂。）同理可以求出c的值。 然后，可以得到符合合唱队的队列是b[i]+c[i]-1(a[i]被重复计算了一次)，而题目要求的合唱队列是：max{b[i]+c[i]-1}
1&=i&=总人数，那么要挑出去多少人也就明白了，即 总人数 -& max{b[i]+c[i]-1
//合唱队形问题:
// 问题描述: 给定一串整数 从中剔除一些数 使得其按从从小到大 再从大到小的顺序排列 如: 1 2 3 6 5 4 要求留下的数字尽可能多
数组大小 数组数据
能得到的最优队列元素个数 并输出元素队列
#include &iostream&
//用于保存子问题最优解的备忘录
typedef struct
//当前子问题最优解
//构造该子问题所用到的下一级子问题序号(用于跟踪输出最优队列)
//用于递归输出Memo B中的解
void Display(int* A, Memo* M, int i)
if (M[i].prev == -1)
cout&&A[i]&&& &;
Display(A, M, M[i].prev);
cout&&A[i]&&& &;
//算法主要部分
void GetBestQuence(int* A, int n)
//定义备忘录 并作必要的初始化
Memo *B = new Memo[n];
//B[i]代表从A[0]到A[i]满足升序剔除部分元素后能得到的最多元素个数
Memo *C = new Memo[n];
//C[i]代表从A[i]到A[n-1]满足降序剔除部分元素后能得到的最多元素个数
B[0].maxlen = 1;
//由于B[i]由前向后构造 初始化最前面的子问题
(元素本身就是一个满足升序降序的序列)
C[n-1].maxlen = 1;
//同样C[i]由后向前构造
for (int i=0; i&n; i++) //为前一个最优子问题序号给定一个特殊标识-1
//用于在跟踪路径时终止递归或迭代(因为我们并不知道最终队列从哪里开始)
B[i].prev = -1;
C[i].prev = -1;
for (i=1; i&n; i++)
//构造B[n]
int max=1;
for (int j=i-1; j&=0; j--)
//查看前面的子问题 找出满足条件的最优解 并且记录
if (A[j]&A[i] && B[j].maxlen+1&max)
max = B[j].maxlen+1;
//跟踪当前最优解
B[i].prev =
//跟踪构造路径
B[i].maxlen =
//构造最优解
for (i=n-1; i&0; i--)
int max=1;
for (int j=i; j&n; j++)
//从后往前构造 这是为了后面在统筹最终解时可以直接用B[i]+C[i]-1
//否则我们得到的最优解始终为B[n-1]+C[n-1]
if (A[j]&A[i] && C[j].maxlen+1&max) //比当前长度更长 记录并构造
max = C[j].maxlen+1;
C[i].prev =
C[i].maxlen =
//遍历i 得到最大的B[i]+C[i]-1(-1是因为我们在B[i]和C[i]中 均加上了A[i]这个数 因此需要减去重复的)
int maxQuence = 0; //记录当前最优解
//记录i 用于跟踪构造路径
for (i=0; i&n; i++)
if (B[i].maxlen+C[i].maxlen-1 & maxQuence)
maxQuence = B[i].maxlen+C[i].maxlen-1;
MostTall =
cout&&&最大合唱队形长度: &&&maxQuence&&
//B由前向后构造 因此prev指向前面的元素 需要递归输出
Display( A, B, MostTall);
//C的prev指向后面元素 直接迭代输出
while (C[MostTall].prev != -1)
MostTall = C[MostTall].
cout&&A[MostTall]&&& &;
delete []B;
delete []C;
int main()
cout&&&请输入合唱队员个数: &&&
A = new int[n];
cout&&&输入队员身高 :&&&
for (int i=0; i&n; i++)
cin&&A[i];
GetBestQuence(A, n);
delete []A;
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：103296次
积分：1435
积分：1435
排名：千里之外
原创：53篇
评论：23条
(1)(1)(1)(2)(3)(3)(4)(3)(13)(22)君，已阅读到文档的结尾了呢~~
第一节整式,整式的加减,整式的乘除,整式的乘法,整式的除法,整式的乘法练习题,整式的乘除测试题,什么是整式,整式的概念,整式的加减练习题,整式方程
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
第一节整式
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口2013年秋七年级(人教版)集体备课教案：2.2整式的加减(3)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
2013年秋七年级(人教版)集体备课教案：2.2整式的加减(3)
||暂无简介
总评分4.1|
浏览量324510
阅读已结束，如果下载本文需要使用5下载券
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢欢迎来到高考学习网，
免费咨询热线：010-
今日：3603套总数：5821315套专访：3238部会员：366765位
当前位置：
& 2012年高考政治冲刺精练36
2012年高考政治冲刺精练36
资料类别: /
所属版本: 通用
上传时间：
下载次数：66次
资料类型：专题资料
文档大小：52KB
所属点数: 0点
【下载此资源需要登录并付出 0 点，】
资料概述与简介
《2.2.2整式的加减（三）》教案
教学目标：
重点：整式的加减。
难点：总结出整式的加减的一般步骤。　
教学过程：
一、复习引入：
1、做一做。
某学生合唱团出场时第一排站了ｎ名，从第二排起每一排都比前一排多一人，一共站了四排，则该合唱团一共有多少名学生参加？
①学生写出答案：ｎ＋（ｎ＋１）＋（ｎ＋２）＋（ｎ＋３）
②提问：以上答案进一步化简吗？如何化简？我们进行了哪些运算？
2、练习：化简：
（1）(x+y)—(2x－3y)
(2)2（a2-2b2）
初中学习网，资料共分享！我们负责传递知识！
让学生自然地认识到整式的化简实质上就是整式的加减。
本网部分资源来源于会员上传，除本网组织的资源外，版权归原作者所有，如有侵犯版权，请联系并提供证据（），三个工作日内删除。
其他相关资源
友情链接：
Copyright &2006 - 2016 高考学习网版权所有. All Rights Reserved.}