动态规划问题

Ranbo_

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，   则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。
已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。



我用的是最长子序列的求法，正向一次遍历最长子序列，反向再遍历一次，正向与反向相加即得到了一个队列中最多的人数，也就是出队最少的人数。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <stdbool.h>
   
4. #include <string.h>
   
5. #define MAX 200
   
6. 
   
7. int main()
   
8. {
   
9.     int n;
   
10.     while(~scanf("%d", &n))
    
11.     {
    
12.         int i, j, max = 0;
    
13.         int inc[MAX], dec[MAX], dp[MAX], stu[MAX];
    
14.         memset(inc, 0, sizeof(int) * MAX);
    
15.         memset(dec, 0, sizeof(int) * MAX);
    
16.         memset(dp , 0, sizeof(int) * MAX);
    
17.         memset(stu, 0, sizeof(int) * MAX);
    
18.         for(i = 0; i < n; i++)
    
19.         {
    
20.             scanf("%d", stu + i);
    
21.             for(j = i - 1; j >= 0; j--)
    
22.             {
    
23.                 if(stu[i] > stu[j] && inc[i] < inc[j] + 1)
    
24.                     inc[i] = inc[j] + 1;
    
25.             }
    
26.         }
    
27.         for(i = n - 1; i >= 0; i--)
    
28.         {
    
29.             for(j = i + 1; j < n; j++)
    
30.             {
    
31.                 if(stu[i] > stu[j] && dec[i] < dec[j] + 1)
    
32.                     dec[i] = dec[j] + 1;
    
33.             }
    
34.             dp[i] = inc[i] + dec[i] + 1;//因为还有自己没算进去，所以要加1
    
35.             if(max < dp[i])
    
36.                 max = dp[i];
    
37.         }
    
38.         printf("%d\n", n - max);
    
39.     }
    
40. 
    
41.     return 0;
    
42. }
    

复制代码