pascal求最长上升子序列(不要递归做的)

发布网友 发布时间：2022-04-25 08:12

我来回答

共2个回答

热心网友 时间：2023-11-08 09:12

用动规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.

热心网友 时间：2023-11-08 09:13

const maxn=1000;
var i,j,b,c,n:longint;
f,g,pre,print:array[1..maxn+1] of longint;
begin
readln(n);
for i:=1 to n do read(g[a]);
f[1]:=1;
g[n+1]:=maxlongint;
for i:=2 to n+1 do
begin
f[i]:=1;
for j:=1 to i-1 do
begin
if (g[i]>g[j]) and (f[i]<f[j]+1) then
begin
f[i]:=f[j]+1;
pre[i]:=j;
end;
end;
end;
b:=pre[n+1];
c:=f[n+1]-1;
repeat
print[c]:=g[b];
dec(c);
b:=pre[b];
until b=0;
for i:=1 to c do write(print[i]);
writeln;
end.

热心网友 时间：2023-11-08 09:12

用动规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.

热心网友 时间：2023-11-08 09:13

const maxn=1000;
var i,j,b,c,n:longint;
f,g,pre,print:array[1..maxn+1] of longint;
begin
readln(n);
for i:=1 to n do read(g[a]);
f[1]:=1;
g[n+1]:=maxlongint;
for i:=2 to n+1 do
begin
f[i]:=1;
for j:=1 to i-1 do
begin
if (g[i]>g[j]) and (f[i]<f[j]+1) then
begin
f[i]:=f[j]+1;
pre[i]:=j;
end;
end;
end;
b:=pre[n+1];
c:=f[n+1]-1;
repeat
print[c]:=g[b];
dec(c);
b:=pre[b];
until b=0;
for i:=1 to c do write(print[i]);
writeln;
end.

热心网友 时间：2023-11-08 09:12

用动规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.

热心网友 时间：2023-11-08 09:12

用动规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.

热心网友 时间：2023-11-08 09:12

用动规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.

热心网友 时间：2023-11-08 09:13

const maxn=1000;
var i,j,b,c,n:longint;
f,g,pre,print:array[1..maxn+1] of longint;
begin
readln(n);
for i:=1 to n do read(g[a]);
f[1]:=1;
g[n+1]:=maxlongint;
for i:=2 to n+1 do
begin
f[i]:=1;
for j:=1 to i-1 do
begin
if (g[i]>g[j]) and (f[i]<f[j]+1) then
begin
f[i]:=f[j]+1;
pre[i]:=j;
end;
end;
end;
b:=pre[n+1];
c:=f[n+1]-1;
repeat
print[c]:=g[b];
dec(c);
b:=pre[b];
until b=0;
for i:=1 to c do write(print[i]);
writeln;
end.

热心网友 时间：2023-11-08 09:13

const maxn=1000;
var i,j,b,c,n:longint;
f,g,pre,print:array[1..maxn+1] of longint;
begin
readln(n);
for i:=1 to n do read(g[a]);
f[1]:=1;
g[n+1]:=maxlongint;
for i:=2 to n+1 do
begin
f[i]:=1;
for j:=1 to i-1 do
begin
if (g[i]>g[j]) and (f[i]<f[j]+1) then
begin
f[i]:=f[j]+1;
pre[i]:=j;
end;
end;
end;
b:=pre[n+1];
c:=f[n+1]-1;
repeat
print[c]:=g[b];
dec(c);
b:=pre[b];
until b=0;
for i:=1 to c do write(print[i]);
writeln;
end.

热心网友 时间：2023-11-08 09:12

用动规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.

热心网友 时间：2023-11-08 09:13

const maxn=1000;
var i,j,b,c,n:longint;
f,g,pre,print:array[1..maxn+1] of longint;
begin
readln(n);
for i:=1 to n do read(g[a]);
f[1]:=1;
g[n+1]:=maxlongint;
for i:=2 to n+1 do
begin
f[i]:=1;
for j:=1 to i-1 do
begin
if (g[i]>g[j]) and (f[i]<f[j]+1) then
begin
f[i]:=f[j]+1;
pre[i]:=j;
end;
end;
end;
b:=pre[n+1];
c:=f[n+1]-1;
repeat
print[c]:=g[b];
dec(c);
b:=pre[b];
until b=0;
for i:=1 to c do write(print[i]);
writeln;
end.

热心网友 时间：2023-11-08 09:13

const maxn=1000;
var i,j,b,c,n:longint;
f,g,pre,print:array[1..maxn+1] of longint;
begin
readln(n);
for i:=1 to n do read(g[a]);
f[1]:=1;
g[n+1]:=maxlongint;
for i:=2 to n+1 do
begin
f[i]:=1;
for j:=1 to i-1 do
begin
if (g[i]>g[j]) and (f[i]<f[j]+1) then
begin
f[i]:=f[j]+1;
pre[i]:=j;
end;
end;
end;
b:=pre[n+1];
c:=f[n+1]-1;
repeat
print[c]:=g[b];
dec(c);
b:=pre[b];
until b=0;
for i:=1 to c do write(print[i]);
writeln;
end.