rbsfan.c

Problem D:合唱队形 Time Limit:1000MS Memory Limit:65536K Total Submit:1237 Accepted:437 Language

#define size 100
int tall[size];/*身高数组*/
int maxup[size];/*以某元素为最大值的最大上升队列个数*/
int maxdown[size];/*以某元素为最大值的最大下降序列个数*/
int maxline[size];/*以某元素为最大值的最大队列个数*/
int out[100];/*测试用例去除元素最小值数组*/

int n,count,casecount,tempt,count2;


void setup()
{
    int m;
    for(count=0;count<n;count++)
    {
        if(count==0)
            maxup[count]=1;
        else
        {
            tempt=1;
            for(m=count-1;m>=0;m--)
        	{
                if(tall[count]>tall[m]&&maxup[m]+1>tempt)
                    tempt=maxup[m]+1;

        	}

            maxup[count]=tempt;

        }


        
    }
}

void setdown()
{
    int m;
    for(count=n-1;count>=0;count--)
    {
        if(count==n-1)
            maxdown[count]=1;
        else
        {
            tempt=1;
            for(m=count+1;m<n;m++)
        	{
                if(tall[count]>tall[m]&&1+maxdown[m]>tempt)
                tempt=1+maxdown[m];
        	}
            maxdown[count]=tempt;
        }
    }
}

int longest()
{
    tempt=0;
    for(count=0;count<n;count++)
    {
        maxline[count]=maxup[count]+maxdown[count]-1;
        tempt=tempt<maxline[count]?maxline[count]:tempt;    	
    }
    return tempt;
}

main()
{
    for(casecount=0;;casecount++)
    {
        scanf("%d",&n);
        if(n==0)
            break;
        else
            for(count=0;count<n;count++)
        	{
                scanf("%d",&tall[count]);
        	}
        

            setup();
            setdown();

            out[casecount]=n-longest();
    }
    for(count2=0;count2<casecount;count2++)
    {
        printf("%d\n",out[count2]);
    }
    getch(); /*******************不要这一行********************************/
}
/*printf("HERE");*/