p1098m.bak

www.vijos.cn上一些习题的参考源码

{
思路非常简单：从左求一遍最长不连续递增子序列，再从右求一遍，二者相加(多加了一个本身）求最大值得max，max需要减1（减去一个本身）然后用n-max
最长不连续递增序列状态转移方程：ll[j]:=max(ll[j],ll[k]+1); 1<=k<j if a[k]<a[j]
ll[j]代表以j为尾的最大不连续递增序列长度
}
program p1098;
const
	MAXN=1000;
var
	a:array[1..MAXN] of integer;
	left,right:array[1..MAXN] of integer;
	n,i,j,k,max:integer;

function max1(a,b:integer):integer;
begin
	if a>=b then max1:=a
	else max1:=b;
end;

begin
	readln(n);
	for i:=1 to n do
		read(a[i]);
	fillchar(left,sizeof(left),0);
	fillchar(right,sizeof(right),0);
	
	left[1]:=1;
	for j:=2 to n do begin
		for k:=1 to j-1 do begin
			if a[k]<a[j] then
				left[j]:=max1(left[j],left[k]+1);
		end;
	end;
	
	right[n]:=1;
	for j:=n downto 2 do begin
		for k:=j-1 downto 1 do begin
			if a[k]<a[j] then
				right[j]:=max1(right[j],right[k]+1);
		end;
	end;
	
	max:=0;
	for i:=1 to n do begin
		if max<left[i]+right[i] then
			max:=left[i]+right[i];
	end;
	
	writeln(n-max+1);
	readln;
end.