using namespace std;
const int maxn=110;
int h[maxn],l[maxn],r[maxn];
//h表示身高,l表示从左到右最长上升子序列,r表示从右到左最长上升子序列
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>h[i];
for(int i=0;i<n;i++)
l[i]=r[i]=1;
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
if(h[i]>h[j] && l[i]<l[j]+1)
l[i]=l[j]+1;
for(int i=n-2;i>=0;i--)
for(int j=n-1;j>i;j--)
if(h[i]>h[j] && r[i]<r[j]+1)
r[i]=r[j]+1;
//求出从左往右跟从右往左的最长上升子序列
int ans=0;
for(int i=0;i<n;i++)
if(ans<(l[i]+r[i]-1))
ans=l[i]+r[i]-1;//因为会将自己多算一次所以减去1
cout<<n-ans<<endl;
//ans存的是一个合乎要求的合唱队的最多人数
// system("pause");
return 0;
}
出列人数最少,也就是说留的人最多,也就是序列最长。
这样分析就是典型的最长上升子序列问题。
其实最长子序列只要一次就可以了(没必要每个人都枚举一遍)。因为最长上升子序列不受中间人的影响。
只要求出从左往右跟从右往左的最长上升子序列,这样答案就是n-max(l[i]+r[i]-1).
复杂度O(n2)。