https://vjudge.net/problem/2082745/origin

在学校里，一个班由n名学生组成。 在上午晨跑之前，同学们在班主任面前排成一条直线。 班主任对同学们的对齐方式不满意; 确实，同学们按照他们的学号顺序排列：1,2,3，......，n，但他们没有按高度对齐。 班主任要求一些同学们离开队伍，作为留在队伍里的同学，不改变他们的位置，形成一条新的队伍，使每个学生可以看到队伍的端点（左或右）。 如果没有任何学生的身高大于等于他的身高，这个学生就会看到队伍的端点。

编写一个程序，知道每个学生的高度，确定必须脱离的学生的最小数量。

Input

第一行输入学生的个数 n ； 
第二行输入n个数，表示学生的身高，每个数之间由空格字符分隔。该行的第k个数字表示第k（1 <= k <= n）个学生的身高 
数据限制： 
•2 <= n <= 1000 
•身高是区间[50,250]的整型数字 

Output

只有一行输出，输出必须脱离的学生的最小数量。

Sample Input

8
186 186 131 200 140 100 197 220

Sample Output

4

---

#include<iostream>
#include<cstring>
using namespace std;int a[1005], n;
int get_left(int x)
{int dp[1000], res = 1;//dp[0]=1;for(int i = 1; i <=x; i++)	{dp[i] = 1;for(int j = i-1; j >= 0; j--)if(a[j] < a[i])dp[i] = max(dp[i], dp[j] + 1);res = max(res, dp[i]);}return res;
}int get_right(int x)
{int dp[1000] = {1}, res = 0;for(int i = x+1; i < n; i++){dp[i] = 1;for(int j = i-1; j > x; j--)if(a[j] > a[i])dp[i] = max(dp[i], dp[j] + 1);res = max(res, dp[i]);}//	cout << "res "<<res << endl;return res;
}int main()
{while(cin >> n){int ans = 0;for(int i = 0; i < n; i++)scanf("%d", a+i);for(int i = 0; i < n; i++){ans = max(ans, get_left(i) + get_right(i));//	cout << get_left(i) << ' ' << get_right(i)  << endl;}ans = n - ans;if(ans < 0) ans = 0;cout << ans;}return 0;
}
//5 1 5 9 5 10