动态规划问题

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位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。



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

#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;
}