NOIP2004提高组合唱队形

May 18, 2008

题目很容易理解，可以去搜索。在RQNOJ中是第26题。

注意题中条件，身高不能相等，然后用求最长不上升序列的方法即可。

PS：很烦RQNOJ答对题就不能提交了。。据说只能用MJ。

program hechang;
var
		n, i, j: longint;
		a: array[1..100] of longint;
		left, right: array[1..100] of longint;
		sum, temp: longint;
		find: boolean;
begin
		assign(input, 'hechang.in');
		reset(input);
		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 := 2 to n do
		begin
				find := false;
				for j := 1 to i - 1 do if (a[j] < a[i]) and (left[j] >= left[i]) then
						begin
								left[i] := left[j];
								find := true;
						end;
				if find then inc(left[i]);
		end;
		for i := n - 1 downto 1 do
		begin
				find := false;
				for j := n downto i + 1 do if (a[j] < a[i]) and (right[j] >= right[i]) then
						begin
								right[i] := right[j];
								find := true;
						end;
				if find then 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);
		close(input);
end.

program hechang;
var
		n, i, j: longint;
		a: array[1..100] of longint;
		left, right: array[1..100] of longint;
		sum, temp: longint;
begin
		assign(input, 'chorus10.in');
		reset(input);
		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);
		close(input);
end.