#include <iostream> #include <string> #include <algorithm> #include <cstdio> using namespace std; const int N = 101; int n; int a[N], b[N], c[N]; //思路:利用状态表示数组b[], c[]分别求出以i结尾的最长上升子序列 和 以i开头的最长下降子序列 int res() { if (n == 0) return 0;//处理边界 for (int i = 0; i < n; i++) { b[i] = 1; c[i] = 1;//均初始化为1,即最短时为自身 } for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a[j] < a[i]) b[i] = max(b[i], b[j] + 1); } }//此时b[]记录完毕 for (int i = n - 1; i >= 0; i--) {//要反向遍历否则会导致依赖的后续状态未被正确计算 for (int j = i + 1; j < n; j++) { if (a[j] < a[i]) c[i] = max(c[i], c[j] + 1); } }//c[]记录完毕 int result = 99; for (int i = 0; i < n; i++) result = min(result, n - b[i] - c[i] + 1); return result; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; cout << res() << endl; return 0; }