动态规划合唱队形
【合唱队形】
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.