4842651_ac_63ms_296k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 51 行

#include<iostream>
using namespace std;
float x[1010];
int q[1010];
int b[1010];
int n;
void testout()
{
	int i;
	for(i=0;i<n;i++) cout<<q[i]<<" ";cout<<endl;
	for(i=0;i<n;i++) cout<<b[i]<<" ";cout<<endl;
}
int main()
{
	int i,j,tmax;
	cin>>n;
	for(i=0;i<n;i++) cin>>x[i];
	q[0]=1;
	for(i=1;i<n;i++)
	{
		int qmax=0;
		for(j=0;j<i;j++)
		{
			if(x[i]>x[j]&&q[j]>qmax) qmax=q[j];
		}
		q[i]=qmax+1;
	}
	b[n-1]=1;
	for(i=n-2;i>=0;i--)
	{
		int bmax=0;
		for(j=n-1;j>i;j--)
		{
			if(x[i]>x[j]&&b[j]>bmax) bmax=b[j];
		}
		b[i]=bmax+1;
	}
	//testout();
	tmax=0;
	for(i=0;i<n;i++)
	{
		if(q[i]+b[i]-1>tmax) tmax=q[i]+b[i]-1;
		for(j=i+1;j<n;j++)
		{
			if(q[i]+b[j]>tmax) tmax=q[i]+b[j];
		}
	}
	cout<<n-tmax<<endl;
	return 0;
}