- 合唱队形
-
1476073873 LV 5 @ 2016-09-21 12:42:51
program project1;
var i,m,n:longint;
a:array[1..100] of longint;
function zuo(kk:longint):longint;
var pp,ii,jj:longint;
aa,bb,cc:array[1..100] of longint;
begin
for ii:=1 to kk do
aa[ii]:=0;
pp:=0;
for ii:=1 to kk do
if a[ii]<=a[kk] then begin pp:=pp+1; aa[pp]:=a[ii]; end;
bb[1]:=1;
for ii:=2 to pp do
for jj:=1 to ii-1 do
if (aa[ii]>=aa[jj]) and (bb[ii]<bb[jj]+1) then bb[ii]:=bb[jj]+1;
zuo:=bb[pp];
for ii:=1 to 100 do
begin
aa[ii]:=0; bb[ii]:=0;
end;
end;
function you(kkk:longint):longint;
var ppp,iii,jjj:longint;
aaa,bbb:array[1..100] of longint;
begin
for iii:=1 to kkk do
aaa[iii]:=0;
ppp:=0;
for iii:=kkk to n do
if a[iii]<=a[kkk] then begin ppp:=ppp+1; aaa[ppp]:=a[iii]; end;
bbb[ppp]:=1;
for iii:=ppp-1 downto 1 do
for jjj:=iii+1 to ppp do
if (aaa[iii]>=aaa[jjj]) and (bbb[iii]<bbb[jjj]+1) then bbb[iii]:=bbb[jjj]+1;
you:=bbb[1];
for iii:=1 to 100 do
begin
aaa[iii]:=0; bbb[iii]:=0;
end;
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
m:=0;
for i:=1 to n do
if (zuo(i)+you(i)-1>m) then m:=zuo(i)+you(i)-1;
writeln(n-m);
end.
2 条评论
-
1476073873 LV 5 @ 2016-10-07 19:05:33
我是bb[i]表示以i为最后一位的最长不下降子序列，aa表示比枚举的这个数小的数，因为只在比枚举的数里找，所以bb【pp】为最长的。然后往右找了一遍，最后把bb【pp】和bbb【1】加起来减去公共的枚举的数，找出最大值，请问这种方法为什么不行，求解
-
@ 2016-10-02 19:36:55
求一个最大上升序列和一个最大下降序列。
pascal
type song=record
h,i,d:integer; end;
var a:array[1..100]of song; ans,n,i,j:integer;
function max(x,y:integer):integer;
begin
if(x>y)then exit(x)
else exit(y);
end;
begin
readln(n);
for i:=1 to n do
begin
read(a[i].h);
a[i].i:=1;
a[i].d:=1;
end;
for i:=1 to n do
for j:=1 to i-1 do
if(a[i].h>a[j].h)then
a[i].i:=max(a[i].i,a[j].i+1);
for i:=n downto 1 do
for j:=n downto i+1 do
if(a[i].h>a[j].h)then
a[i].d:=max(a[i].d,a[j].d+1);
ans:=2;
for i:=1 to n do
if(ans<a[i].i+a[i].d) then
ans:=a[i].i+a[i].d;
write(n-ans+1);
end.
- 1
