讨论 / c++ 题解
hzicong 2013-11-07 15:52:11
点我顶贴 收藏 删除
#include<iostream>

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)。

查看更多回复
提交回复