UC知道pascal求最长上升子序列(不要递归做的)
来源：百度知道 编辑：UC知道 时间：2024/06/19 22:04:30
问题描述
设有一个正整数的序列：b1,b2,…，bn，对于下标i1<i2<…＜im，若有bi1≤bi2≤…≤bim
则称存在一个长度为m的不下降序列。
例如，下列数列
13 7 9 16 38 24 37 18 44 19 21 22 63 15
对于下标i1=1，i2=4，i3=5，i4=9，i5=13，满足13＜16＜38＜44＜63,则存在长度为5的不下降序列。
但是，我们看到还存在其他的不下降序列: i1=2，i2=3，i3=4，i4=8，i5＝10，i6=11，i7=12，i8=13，满足：7＜9＜16＜18＜19＜21＜22＜63，则存在长度为8的不下降序列。
问题为：当b1,b2,…，bn给出之后，求出最长的不下降序列。
不要递归.求个数我会了.但不知道怎么找到那个序列.知道的帮忙写哈,思路和程序都可以,程序的话输出那个序列就好.谢谢了~
设有一个正整数的序列：b1,b2,…，bn，对于下标i1<i2<…＜im，若有bi1≤bi2≤…≤bim
则称存在一个长度为m的不下降序列。
例如，下列数列
13 7 9 16 38 24 37 18 44 19 21 22 63 15
对于下标i1=1，i2=4，i3=5，i4=9，i5=13，满足13＜16＜38＜44＜63,则存在长度为5的不下降序列。
但是，我们看到还存在其他的不下降序列: i1=2，i2=3，i3=4，i4=8，i5＝10，i6=11，i7=12，i8=13，满足：7＜9＜16＜18＜19＜21＜22＜63，则存在长度为8的不下降序列。
问题为：当b1,b2,…，bn给出之后，求出最长的不下降序列。
不要递归.求个数我会了.但不知道怎么找到那个序列.知道的帮忙写哈,思路和程序都可以,程序的话输出那个序列就好.谢谢了~
用动规dp的
这就是最长不降序列的problem
pascal：
program maxlong;
var n,i,j,k,l:integer;
b:array[1..100,1..3] of integer;
begin
writeln('Input N:');
readln(n);
for i:=1 to n do
begin
read(b[i,1]);
b[i,2]:=1;
b[i,3]:=0;
end;
for i:=n-1 downto 1 do
begin
l:=0; k:=0;
for j:=i+1 to n do
if (b[j,1]>b[i,1]) and (b[j,2]>l) then begin
l:=b[j,2];
k:=j;
end;
if l>0 then begin
b[i,2]:=l+1; b[i,3]:=k;
end;
end;
k:=1;
for j:=1 to n do
if (b[j,2]>b[k,2]) then k:=j;
writeln('Max=',b[k,2]);
while k<>0 do
begin
write(b[k,1]:4);
k:=b[k,3];
end;
writeln;
end.
dp
const maxn=1000;
var i,j,b,c,n:longint;
f,g,pre,print:arr