算法1
DP $O(n^2)$
做两次最长上升子序列 一次从前往后用l[] 一次从后往前r[]
最长上升子序列 :
数据量较小 可以用朴素做法O(n2n2)
l[i]表示的是从第一个数字开始以a[i]为结尾的最长上升子序列的最大长度
所以我们对每个i枚举j (保证j比i小 因为l[i]是以a[i]为结尾的最长上升子序列长度
在a[i] > a[j]时,l[i] = max(l[i], l[j] + 1)
这样求出l[] r[]数组后 我们枚举每一个i 相当于枚举合唱队中最中间的人的身高 然后用总数减去l[i]+r[i]即可
注意答案要+1 因为 减的时候会多减去一个重复的人 也就是中间的人
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int l[N],r[N],a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
l[i] = 1;
for(int j=1;j<i;j++)
if(a[i] > a[j]) l[i] = max(l[i],l[j] + 1);
}
for(int i=n;i>=1;i--)
{
r[i] = 1;
for(int j=n;j>i;j--)
if(a[i] > a[j]) r[i] = max(r[i],r[j] + 1);
}
int res=INT_MAX;
for(int i=1;i<=n;i++)
res = min(res,n-l[i]-r[i]+1);
cout<<res;
}