合唱队形(DP)-白红宇

合唱队形(DP)

阅读量：6941 次

发布时间：2019-06-27

本文共 1166 字，大约阅读时间需要 3 分钟。

【题目】

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，

他们的身高分别为T1，T2，…，TK，则他们的身高满足 T1 < T2 ...< Ti > Ti+1 > … >TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入格式】

第一行是一个整数N(2<=N<=100)，表示同学的总数。

下来n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

【输出格式】

包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【样例输入】

186 186 150 200 160 130 197 220

【样例输出】

思路：

　　正着求一遍最长上升子序列和反着求一遍最长上升子序列即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             10 #include
              
               11 #include
               
                12 #include
                
                 13 #include
                 
                  14 #define ll long long int15 #define INF 0x7fffffff16 #define mod 100000000717 #define me(a,b) memset(a,b,sizeof(a))18 #define PI acos(-1.0)19 #define mian main20 //size_t npos=-1;21 //ios::sync_with_stdio(0),cin.tie(0);22 using namespace std;23 const int N=1e5+5;24 25 int main()26 {27 int n,a[105],dp1[105],dp2[105];28 cin>>n;29 for(int i=0;i
                  
                   >a[i];31 for(int i=0;i
                   
                    =0;i--){39 dp2[i]=1;40 for(int j=n-1;j>i;j--){41 if(a[j]