P1067 （C++代码）

解题思路:





注意事项:





参考代码:

#include<iostream>
#include<cmath>
using namespace std;
int num[1010];//每个人的身高 
int ans=1;//最后留下的人数 
int sum1[1010],sum2[1010];//升序列和降序列中留下的人数 
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
      cin>>num[i];//输入 
      sum1[i]=1;//留下的人数，至少为1 
      sum2[i]=1;}
    for(int i=1;i<=n;i++)
      for(int j=1;j<i;j++)
        if(num[i]>num[j])//如果i位置的值大于j位置的，这是可以作为上升子序列 
        sum1[i]=max(sum1[i],sum1[j]+1);//比较不取i位置和取i位置哪个留下的人多 
    for(int i=n;i>=1;i--)//最小降序列，反着枚举 
      for(int j=n;j>i;j--)
        if(num[i]>num[j])
        sum2[i]=max(sum2[i],sum2[j]+1);
    for(int i=1;i<=n;i++)
        ans=max(ans,(sum2[i]+sum1[i]-1));//ans是留下的人数，和每一种方案留下的人数比较。减一是中间的人重复计数。 
    cout<<n-ans<<endl;//n是总人数，ans留下的人数 
    return 0;
}