一等队形

** 一等队形：** <Excerpt in index | 首页摘要>

<The rest of contents | 余下全文>

一等队形
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 150(49 users) Total Accepted: 65(45 users) Rating: Special Judge: No
Description
N位士兵站成一排，长官要请其中的(N-K)位出列，使得剩下的K位士兵排成一等队形。一等队形是指这样的一种队形：设K位士兵从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<…<Ti，Ti>Ti+1>…>TK(1<=i<=K)。 你的任务是，已知所有N位士兵的身高，计算最少需要几位士兵出列，可以使得剩下的排成一等队形。

Input
多组输入数据。

输入的第一行是一个整数N(2<=N<=100)，表示士兵的总数。第二行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位士兵的身高(厘米)。

Output
输出一个数代表最少需要几位士兵出列。

Sample Input
8
186 186 150 200 160 130 197 220
Sample Output
4
Source
2014 Winter Holiday Contest 2

弄过了好长时间。。。。

Code

#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
int a[101];
int b[101];
int c[101];
int N;
void check()
{
int i,j;
for(i=0;i<N;i++)
{
    b[i]=1;
for(j=0;j<i;j++)
{
if(a[i]>a[j]&&b[j]+1>b[i])
{
    b[i]=b[j]+1;
}
}
//cout<<b[i]<<endl;
}
for(i=N-1;i>=0;i--)
{
    c[i]=1;
for(j=N-1;j>i;j--)
{
if(a[j]<a[i]&&c[j]+1>c[i])
{
    c[i]=c[j]+1;
}
}
//cout<<c[i]<<endl;
}
}
int min1(int x,int y)
{
return x<y? x:y;
}
int max1(int x,int y)
{
return x>y? x:y;
}
int main()
{
while(~scanf("%d",&N))
{
if(N==2)
{
int x,y;
    scanf("%d%d",&x,&y);
if(x==y)
{
    printf("1\n");
}
else
{
    printf("0\n");
}
continue;
}
int i;
for(i=0;i<N;i++)
{
    scanf("%d",&a[i]);
}
    check();
int j,k;
int max_left=INT_MIN,max_right=INT_MIN;
int min=INT_MAX;
// cout<<min<<endl;
for(i=0;i<N;i++)
{
    min=min1(min,N-b[i]-c[i]+1);
}
    printf("%d\n",min);
}
return 0;
}