思路:输出n-max(max_len(递增),max_len(递减));
是否是DP错了.............-_____________________________________-

#include <iostream>
using namespace std;
int cow[30001],n,n1=0,n2=0,n3=0;
struct dpp
{
	int len,back;
}dp[30001];
void solve()
{
	int i,j,len;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&cow[i]);
		if(cow[i]==1)
			n1++;
		if(cow[i]==2)
			n2++;
		if(cow[i]==3)
			n3++;
	}
	if(n1==n||n2==n||n3==n)
		{
			cout<<0<<endl;
			return;
		}
	for(i=1;i<=n;i++)
		dp[i].len=1;
	dp[0].back=0;
	for(i=1;i<=n;i++)
		{
			if(cow[i]>=dp[i-1].back)
			{
				dp[i].len=dp[i-1].len+1;		
				dp[i].back=cow[i];
			}
			else
				{
					for(j=1;j<=i-2;j++)
						if(cow[i]>=dp[j].back)
							if(dp[j].len+1>dp[i].len)
								dp[i].len=dp[j].len+1;	
					dp[i].back=cow[i];
				}
		}
	len=dp[n].len;
	for(i=1;i<=n;i++)
		dp[i].len=1;
	dp[0].back=cow[1];
	dp[0].len=0;
	for(i=1;i<=n;i++)
		{
			if(cow[i]<=dp[i-1].back)
			{
				dp[i].len=dp[i-1].len+1;		
				dp[i].back=cow[i];
			}
			else
				{
					for(j=1;j<=i-2;j++)
						if(cow[i]<=dp[j].back)
							if(dp[j].len+1>dp[i].len)
								dp[i].len=dp[j].len+1;	
					dp[i].back=cow[i];
				}
		}
	len=len>dp[n].len?len:dp[n].len;
	cout<<n-len<<endl;
}
int main()
{
	solve();
    return 0;    
}