4842330_wa.cpp

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

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