合唱队形.cpp

N位同学站成一排

#include<stdio.h>
int max(int a[],int n)
{
	int i,max=a[0];
	for(i=1;i<n;i++)
	{
		if(a[i]>max) max=a[i];
	}
	return max;
}
int up(int a[],int i,int left[])
{
	int j,temp=0,loc;
	if(i==0) return 0;
    for(j=0;j<i;j++)
	{
		if(a[i]>a[j]&&(a[j]>temp||left[j]>left[loc])) 
		{
			loc=j;
			temp=a[j];
			left[i]=left[j]+1;
//		    printf("%d",left[i]);
		}
	}
	return left[i];
}
int down(int a[],int i,int n,int right[])
{
	int j,temp,loc;
	if(i==n-1) return 0;
    for(j=n-1;j>i;j--)
	{
		if(a[i]>a[j]&&(a[j]>temp||right[j]>right[loc])) 
		{
			loc=j;
			temp=a[j];
			right[i]=right[j]+1;
		}
	}
	return right[i];
}

int main()
{
	int i,j=0,n,h[100];
	int sum[100],min[100];
	scanf("%d",&n);
	while(n!=0)
	{
		int left[100]={0},right[100]={0};
		for(i=0;i<n;i++)
		{
			scanf("%d",&h[i]);
		}
		for(i=0;i<n;i++)
		{
			left[i]=up(h,i,left);
		}
//		for(i=0;i<n;i++)
//			printf("%-3d ",left[i]);
//		printf("\n");

		for(i=n-1;i>=0;i--)
		{
			right[i]=down(h,i,n,right);
			sum[i]=right[i]+left[i];
		}
//		for(i=0;i<n;i++)
//			printf("%-3d ",right[i]);
//		printf("\n");
	    min[j++]=n-max(sum,n)-1;
//        printf("%d\n",min[j-1]);
        scanf("%d",&n);
	}
	for(i=0;i<j;i++)
	{
	   printf("%d\n",min[i]);
	}
    return 0;
}