记录编号	164138	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]合唱队形	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-05-28 17:50:45	内存使用	0.31 MiB

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <fstream>
#define cin fin
#define cout fout
 
using namespace std;

ifstream fin("chorus.in");
ofstream fout("chorus.out");
const short MAXN = 101;
short n, dp1[MAXN] = {0}, dp2[MAXN] = {0}, h[MAXN], maxx = 0;
 
void init()
{
    cin >> n;
    memset(dp1, 0, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));
    for(short i = 1; i <= n; i ++)
        cin >> h[i];
    return;
}
 
void Dynamic_Programming()
{
    dp1[1] = 1;
    for(short i = 2; i <= n; i ++)
    {
        for(short j = 1; j < i; j ++)
            if(h[j] < h[i])
                dp1[i] = max(dp1[i], dp1[j]);
        dp1[i] ++;
    }
     
    dp2[n] = 1;
    for(short i = n - 1; i >= 1; i --)
    {
        for(short j = i + 1; j <= n; j ++)
            if(h[j] < h[i])
                dp2[i] = max(dp2[i], dp2[j]);
        dp2[i] ++;
    }
    return;
}
 
int main()
{
    ios::sync_with_stdio(false);
    init();
     
    Dynamic_Programming();
    for(short i = 1; i <= n; i ++)
        if(dp1[i] + dp2[i] > maxx)
            maxx = dp1[i] + dp2[i];
     
    cout << n - maxx + 1;
//  system("pause");
    return 0;
}