|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足存在i(1<=i<=K)使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。
已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
我用的是最长子序列的求法,正向一次遍历最长子序列,反向再遍历一次,正向与反向相加即得到了一个队列中最多的人数,也就是出队最少的人数。
- #include <stdio.h>
- #include <stdlib.h>
- #include <stdbool.h>
- #include <string.h>
- #define MAX 200
- int main()
- {
- int n;
- while(~scanf("%d", &n))
- {
- int i, j, max = 0;
- int inc[MAX], dec[MAX], dp[MAX], stu[MAX];
- memset(inc, 0, sizeof(int) * MAX);
- memset(dec, 0, sizeof(int) * MAX);
- memset(dp , 0, sizeof(int) * MAX);
- memset(stu, 0, sizeof(int) * MAX);
- for(i = 0; i < n; i++)
- {
- scanf("%d", stu + i);
- for(j = i - 1; j >= 0; j--)
- {
- if(stu[i] > stu[j] && inc[i] < inc[j] + 1)
- inc[i] = inc[j] + 1;
- }
- }
- for(i = n - 1; i >= 0; i--)
- {
- for(j = i + 1; j < n; j++)
- {
- if(stu[i] > stu[j] && dec[i] < dec[j] + 1)
- dec[i] = dec[j] + 1;
- }
- dp[i] = inc[i] + dec[i] + 1;//因为还有自己没算进去,所以要加1
- if(max < dp[i])
- max = dp[i];
- }
- printf("%d\n", n - max);
- }
- return 0;
- }
复制代码
|
|