UC知道pascal 合唱队形
来源：百度知道 编辑：UC知道 时间：2024/06/02 20:31:11
程序我带了
一定要包教懂啊
教的好再加分
____________________
咳～此题是一道典型的动态规划题目（DP）
其动态转移方程如下
Up[i]=max{up[j]+1((0<j<i) and a[j]<a[i]),up[i-1]}
Down[i]=max{down[j]+1((i<j<n) and a[j]<a[i],down[i+1]}
即做从左和从右的两次最长最降子序列。
最后答案为Max{Up[i]+Down[i]-1(0<i<n+1)}
程序应该不难懂，如果实在不懂的话请补充问题，我再来具体解释～！
程序如下：
program ZAX;
var a,a1,a2:array[1..100] of integer;
i,j,max,min,tmp,n:integer;
begin
readln(n);for i:=1 to n do read(a[i]);min:=101;
for i:=1 to n do begin
j:=i-1;max:=0;
while j>=1 do begin
if (a[j]<a[i])and(a1[j]>max)then ax:=a1[j];dec(j);
end;
a1[i]:=max+1;
end;
for i:=n downto 1 do begin
j:=i+1;max:=0;
while j<=n do begin
if (a[j]<a[i])and(a2[j]>max)then ax:=a2[j];inc(j);
end;
a2[i]:=max+1;
end;
for i:=1 to n do begin
tmp:=n+1-(a1[i]+a2[i]);if tmp&
呵呵。我们先瞥开dp不看。解决这个问题我们这么考虑：
肯定有一个中间人，然后在他左边的人都要比他矮，并且是单调上升；在他右边的人肯定要比他矮，并且是单调下降！那么我们有了这个中间人，并且知道他的身高和他的位置，然后就是做左边的最长单调上升序列，加上右边的最长单调下降序列！
这个中间人，我们来枚举他，那么是不是只要解决最长单调上升序列和最长单调下降序列了？
这个单调上升序列和单调下降序列就用dp来求解！求解单调下降序列其实就是把一个数列反过来求最长单调上升序列吧？那么我就来讲一下单调上升序列。
给一个序列，求最长单调上升序列，我们用up[i]表示从第一个人到第i个人，最长的序列长。（就是到第i个人，必须身高单调上升，最多取多少人）
显然up[1]=1。
up[2]等于什么？如果2这个人比1高，那么up[2]=up[1]+1，要不就等于1是吧？
我们知道了up[1]和up[2]能不能知道up[3]呢？当然可以！因为如果3的人比2高，那么up〔3〕的值就可以取up[2]+1！
于是我们可以得出结论：
第i个人如果比第j个人高（i>j），那么up[i]就可以取up[j]+1！
那么就得出：
Up[i]=max{up[j]+1((0<j<i) and a[j]<a[i]),up[i-1]}
这里你还要注意一个问题，就是求出这个，但是a[i]必须小于中间人高度，这个up[i]才可取～
理解了么？
我们枚举一个中间人，ans=左边最长单调上升序列＋右边最长单调下降序列＋1(1就是中间这个人)
一个中间人对应一个ans，枚举中间人，求出最大的ans
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
我觉得说得很清楚了丫，up[i]表示到第i个人的最长上升子序列。
如果a[i]>a[j](i>j),那么up[i]的值就可以取up[j]+1（就是到第i个人的最长上升子序列加上第i个人）
于是我们对所有i，对j做一个循环。
得出Up[i]=max{up[j]+1((0<j<