嗯...

 

题目链接：

很明显这是一道dp题，求最长上升/下降子序列...

但这道题中既有上升序列，也有下降序列，所以我们把 f 数组设成二维，f[i][1]表示开始的上升子序列，f[i][2]表示后来的下降子序列（其实可以开两个数组）。依次枚举每一个点，把它当做中间最高的那一个，然后求出它的最长上升/下降子序列，最后枚举一遍，找一个最长的即可。

 

动态转移方程（首先要判断是否符合上升/下降）：

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

 

AC代码：

1 #include
      
        2 #include
       
         3  4 using namespace std; 5  6 int f[305][3], t[105], ans; 7  8 int main(){ 9     int n;10     scanf("%d", &n);11     for(int i = 1; i <= n; i++)12         scanf("%d", &t[i]);13     for(int i = 1; i <= n; i++){14         for(int j = 0; j < i; j++){15             if(t[j] < t[i]) f[i][1] = max(f[i][1], f[j][1] + 1);//首先要判断 16         }17     }     18     for(int i = n; i >= 1; i--){19         for(int j = n + 1; j > i; j--){20             if(t[i] > t[j]) f[i][2] = max(f[i][2], f[j][2] + 1);21         }22     }23     for(int i = 1; i <= n; i++){24         ans = max(ans, f[i][2] + f[i][1] - 1);//ans是队列中人数 25     }26     printf("%d\n", n - ans);27     return 0;28 }