这题的状态转移方程为dp[i]=max(dp[i]，dp[j]+1)

因而可以有代码

#include<iostream>

#include<algorithm>

using namespace std;

int arr[102][2];

int a[102];

int main()

{

 int n;

 cin >> n;

 for (int i = 1; i <= n; i++)

 {

  cin >> a[i];

 }

 for (int i = 1; i <= n; i++)//循环求出最长的升序列

 {

  arr[i][0] = 1;

  for (int j = 1; j <= i; j++)

  {

   if (a[i] > a[j])

    arr[i][0] = max(arr[i][0], arr[j][0] + 1);//这里的arr[j][0]是不包括j自己的

                                                          //所以要+1

  }

 }

 for (int i = 1; i <= n; i++)//求出最长的序列

 {

  arr[i][1] = 1;

  for (int j = 1; j <= i; j++)

  {

   if (a[i] < a[j])

    arr[i][1] = max(arr[i][1], max(arr[j][0], arr[j][1]) + 1);

  }

 }

 int ans = 0;

 for (int i = 1; i <= n; i++)

 {

  ans = max(ans, max(arr[i][0], arr[i][1]));

 }

 cout << n - ans << endl;

 system("pause");

 return 0;

}