算法1
DP-最长上升子序列变种
时间复杂度 O(n^2)
思路:根据题意,要求最少的人出列,就是要留下最多的人,刚好符合最长上升子序列中的”最长”,因为题目中要求有一个最高点,所以说要想办法找出这个最适合的点,使得这个点:左边的上升子序列 + 右边的上升子序列 和最大。
有了这个想法,我们可以先处理出来从左往右以每一个点结尾的上升子序列的长度,以及从右往左以每一个点结尾的上升子序列的长度,最后将每个点两边的长度相加,就是以这个点为最高点的时候队形的总长度,即留下的人数。
令f1表示从左往右,f2表示从右往左,f1[i]表示的是以i这个点为结尾的最长上升子序列的长度,状态转移方程为:
f1[i] = max(f[i], f[j] + 1),j代表从1~i-1枚举的指针,f2同理。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int a[N], f1[N], f2[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j < i; j ++ )
if (a[i] > a[j]) f1[i] = max(f1[i], f1[j] + 1);
}
for (int i = n; i >= 1; i -- )
{
for (int j = n; j > i; j -- )
if (a[i] > a[j]) f2[i] = max(f2[i], f2[j] + 1);
}
int res = 0;
for (int i = 1; i <= n; i ++ ) f1[i] += f2[i];
for (int i = 1; i <= n; i ++ ) res = max(res, f1[i]);
cout << n - res - 1 << endl;
return 0;
}