动态规划问题
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, dec, dp, stu;
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 > stu && inc < inc + 1)
inc = inc + 1;
}
}
for(i = n - 1; i >= 0; i--)
{
for(j = i + 1; j < n; j++)
{
if(stu > stu && dec < dec + 1)
dec = dec + 1;
}
dp = inc + dec + 1;//因为还有自己没算进去，所以要加1
if(max < dp)
max = dp;
}
printf("%d\n", n - max);
}
return 0;
}
页:
[1]