vijos-p1098合唱队形有谁会做?

发布网友发布时间：2024-09-06 00:07

共2个回答

热心网友时间：2024-10-25 00:47

var a:array[1..100] of integer;b:array[1..100,1..3] of integer;
c,d,n,k:integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x
else max:=y;
end;
begin
readln(n);
for c:=1 to n do read(a[c]);
for c:=1 to n do b[c,1]:=1;
for c:=1 to n do b[c,2]:=0;
for c:=2 to n do
for d:=1 to c-1 do
if a[c]>a[d] then b[c,1]:=max(b[c,1],b[d,1]+1);
for c:=n-1 downto 1 do
for d:=n downto c+1 do
if a[d]<a[c] then b[c,2]:=max(b[c,2],b[d,2]+1);
for c:=1 to n do b[c,3]:=b[c,2]+b[c,1];
k:=b[1,3];
for c:=2 to n do
if b[c,3]>k then k:=b[c,3];
writeln(n-k);
end.
这个是我在vijos上的程序，AC了。。。。
思路就是先从前往后求最长不下降子序列,然后再从后往前求一次,之后将两次求的数组对应相加,再用总的N减去加完的每一个数,得到的最小值就是要求的了

热心网友时间：2024-10-25 00:48

给程序，思路就是最长不降子序列
var
n, i, j: longint;
a: array[1..100] of longint;
left, right: array[1..100] of longint;
sum, temp: longint;
begin
sum := 0;
readln(n);
for i := 1 to n do read(a[i]);
readln;
fillchar(left, sizeof(left), 0);
fillchar(right, sizeof(right), 0);
for i := 1 to n do
begin
for j := 1 to i - 1 do if (a[j] < a[i]) and (left[j] >= left[i]) then
begin
left[i] := left[j];
end;
inc(left[i]);
end;
for i := n downto 1 do
begin
for j := n downto i + 1 do if (a[j] < a[i]) and (right[j] >= right[i]) then
begin
right[i] := right[j];
end;
inc(right[i]);
end;
for i := 1 to n do
begin
temp := left[i] + right[i];
if temp > sum then
begin
sum := temp;
end;
end;
writeln(n - sum + 1);
end.

希望对你有帮助！！