1264：【例9.8】合唱队形 2021-01-15

1. #include <iostream>
2. #include <cstdio>
3. using namespace std;
4. int a[200],b[200],c[200];
5. int main(int argc, char *argv[])
6. {
7.  int n,i,j,maxx;
8.  cin>>n;
9.  for(i=1;i<=n;i++) cin>>a[i];
10.   //b[i]从左到右满足身高递增的人数 
11.   for(i=1;i<=n;i++){
12.     b[i]=1;
13.     for(j=1;j<=i-1;j++)
14.       if((a[i]>a[j])&&(b[j]+1>b[i]))
15.         b[i]=b[j]+1;
16.   }
17. 
18. //  for(i=1;i<=n;i++)cout<<b[i]<<" ";
19. //  cout<<endl;
20. 
21.   //c[i]从右到左满足身高递增的人数
22.   for(i=n;i>=1;i--){
23.     c[i]=1;
24.     for(j=i+1;j<=n;j++)
25.       if((a[j]<a[i])&&(c[j]+1>c[i]))
26.         c[i]=c[j]+1;
27.   }
28. 
29. //  cout<<endl;
30. //  for(i=1;i<=n;i++)cout<<c[i]<<" ";
31. //  cout<<endl;
32. 
33.   //统计同时满足最优的最大数量 
34.   maxx=0;
35.   for(i=1;i<=n;i++)
36.     if(b[i]+c[i]>maxx)
37.       maxx=b[i]+c[i];
38.   //减去被重复使用的i同学 
39.   cout<<n-maxx+1<<endl;
40.   return 0;
41. }