合唱队形（动规，最长不下降子序列）

 1 //合唱队形 (同登山)
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 using namespace std;
 6 const int maxx=101;
 7 int a[maxx],b[maxx],c[maxx];
 8 int main()
 9 {
10     int n;
11     scanf("%d",&n);
12     for(int i=1;i<=n;i++)
13     scanf("%d",&a[i]);
14     for(int i=1;i<=n;i++)
15     {
16         b[i]=1;
17         for(int j=1;j<=i-1;j++)
18         {
19             if(a[j]<a[i]&&b[i]<b[j]+1)
20             b[i]=b[j]+1;
21         }
22     }
23     for(int i=n;i>=1;i--)
24     {
25         c[i]=1;
26         for(int j=i+1;j<=n;j++)
27         {
28             if(a[j]<a[i]&&c[i]<c[j]+1)
29             c[i]=c[j]+1;
30         }
31     }
32     int maxl=0;
33     for(int i=1;i<=n;i++)
34      if(c[i]+b[i]>maxl)
35      maxl=c[i]+b[i];
36      printf("%d",n-maxl+1);
37      return 0;
38 }