p1098m.pas

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,m: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]);
	{注意动归的初始状态}
	for i:=1 to n do begin
		left[i]:=1;
		right[i]:=1;
	end;
	
	{->从左往右递推}
	{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-1 downto 1 do begin
		for k:=n downto j+1 do begin
			if a[k]<a[j] then
				right[j]:=max1(right[j],right[k]+1);
		end;
	end;
	
	m:=0;
	for i:=1 to n do begin
		if m<left[i]+right[i] then
			m:=left[i]+right[i];
	end;
	
	writeln(n-m+1);
end.