【NOIP2004】【Luogu1091】合唱队形

problem

solution

codes

#include<iostream>
using namespace std;
int h[110],f[110],f2[110], ans;
int main(){
    int n; cin>>n;
    for(int i = 1; i <= n; i++)cin>>h[i];
    for(int i = 1; i <= n; i++){
        int t = 0;
        for(int j = 1; j < i; j++)
            if(h[j]<h[i] && f[j]>f[t])
                t = j;
        f[i] = max(f[i],f[t]+1);
    }
    for(int i = n; i >= 1; i--){
        int t = 0;
        for(int j = n; j > i; j--)
            if(h[j]<h[i] && f2[j]>f2[t])
                t = j;
        f2[i] = max(f2[i],f2[t]+1);
        ans = max(ans,f[i]+f2[i]-1);
    }
    cout<<n-ans<<"\n";
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80404192