codeves天梯 合唱队形

本文主要是介绍codeves天梯 合唱队形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

    合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，  则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

    你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

分析：题目不难，其实题目就是要满足由中间一名同学为最高两边递减身高的队形，可以理解为跑两次最长不下降序列，这里数据水所以直接用了n方的最长不下降（其实用nlogn就快得飞起==）。

constmaxn=100;varn,i,j,max:longint;a,f,v:array[1..maxn] of longint;beginreadln(n);for i:=1 to n doread(a[i]);f[1]:=1;for i:=2 to n dobeginmax:=1;for j:=1 to i-1 doif (a[j]<a[i]) and (f[j]+1>max) thenmax:=f[j]+1;f[i]:=max;end;v[n]:=1;for i:=n-1 downto 1 dobeginmax:=1;for j:=i+1 to n doif (a[j]<a[i]) and (v[j]+1>max) thenmax:=v[j]+1;v[i]:=max;end;max:=0;for i:=1 to n doif f[i]+v[i]>max thenmax:=f[i]+v[i];writeln(n-max+1);
end.

这篇关于codeves天梯 合唱队形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---