首页 动态规划合唱队形

动态规划合唱队形

举报
开通vip

动态规划合唱队形动态规划合唱队形 【合唱队形】 N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足T1Ti+1>…>TK(1<=i<=K)。 你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。 【输入文件】 输入文件chorus.in的第一行是一个整数N(2<=N<=100),表示同学的总数。第二行有n个整数,用空...

动态规划合唱队形
动态规划合唱队形 【合唱队形】 N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。 你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。 【输入文件】 输入文件chorus.in的第一行是一个整数N(2<=N<=100),表示同学的总数。第二行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。 【输出文件】 输出文件chorus.out包括一行,这一行只包含一个整数,就是最少需要几位同学出列。 【样例输入】 8 186 186 150 200 160 130 197 220 【样例输出】 4 【数据规模】 对于50,的数据,保证有n<=20; 对于全部的数据,保证有n<=100。 【分析】 假设第i位同学为最高个,则对其左边序列求最长递增序列长度,对其右边序列求最长递减序列长度,然后两者相加再减1(因为第i位同学被重复计算了一次)即可得到整个合唱队形的长度。可以利用两次动态规划求解,时间效率为O(N2) 依次枚举每一位同学为最高个,则N次之枚举后得到N个合唱队形长度,取其中最大值,然后(N-合唱队形最大值)即所求。 这样总的时间效率为O(N3) 解 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 思路 此题用动态规划来解,首先用数组a保存所有人的身高,第一遍正向扫描找出其中最大的升序子序列,用数组b保存每个人在子序列中的位置,然后反向扫描出其中最大的降序子序列,将结果保存在数组c中,最后将b,c数组对应元素相加,求出最大值,此值即为留下的人数,则n-m为出列的人数。 参考代码 program Chorus; const maxn=200; type data=array[1..maxn] of longint; var a,b,c:data; i,j,n,m:longint; procedure up(x:longint); var i,max:longint; begin max:=0; for i:=x-1 downto 1 do if a[i]max then mx:=b[i]; b[x]:=max+1; end; procedure down(x:longint); var i,max:longint; begin max:=0; for i:=x+1 to n do if a[i]mx then max:=c[i]; c[x]:=max+1; end; begin readln(n); for i:=1 to n do read(a[i]); for i:=1 to n do up(i); for i:=n downto 1 do down(i); m:=0; for i:=1 to n do begin b[i]:=b[i]+c[i]; if b[i]>m then m:=b[i]; end; writeln(n-m+1); end.
本文档为【动态规划合唱队形】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_358746
暂无简介~
格式:doc
大小:14KB
软件:Word
页数:0
分类:生活休闲
上传时间:2017-09-26
浏览量:12