合唱队形

#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
#define MAX 32767
#define MIN -32767
int b[105][105] = {0}; //用于构造最长公共子序列
int c[105][105] = {0}; //记录最长公共子序列长度
int normal[105] = {0}; //记录身高序列
int n; //记录身高序列的长度
int increase[105] = {0}; //记录递增序列
int decrease[105] = {0}; //记录递减序列
int temp1[105] = {0}; //记录最长递增子序列
int count1 = 0; //记录最长递增子序列的长度
int temp2[105] = {0}; //记录最长递减子序列
int count2 = 0; //记录最长递减子序列的长度
int m1 = 0, m2 = 0; //分别记录递增和递减序列的长度

//排序函数的一个参数，逆序用的

int cmp(int aa, int bb) {
    return aa>bb;
}
//求最长公共子序列

void LCSLength(int x[], int y[], int m, int n) {
//    for (int i = 0; i <= m; i++) {
//        c[i][0] = 0;
//    }
//    for (int i = 0; i <= n; i++) {
//        c[0][i] = 0;
//    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i - 1] == y[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 0;
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i][j] = 1;
            } else {
                c[i][j] = c[i][j - 1];
                b[i][j] = -1;
            }
        }
    }
}
//构造最长公共子序列，递增

void printLCS1(int x[], int m, int n, int temp[]) {
    int i = m;
    int j = n;
    if (i == 0 || j == 0) {
        return;
    }
    if (b[i][j] == 0) {
        printLCS1(x, i - 1, j - 1, temp);
        temp[count1++] = x[i - 1];
        // printf("%d ", x[i - 1]);
    } else if (b[i][j] == 1) {
        printLCS1(x, i - 1, j, temp);
    } else {
        printLCS1(x, i, j - 1, temp);
    }
}
//构造最长公共子序列，递减

void printLCS2(int x[], int m, int n, int temp[]) {
    int i = m;
    int j = n;
    if (i == 0 || j == 0) {
        return;
    }
    if (b[i][j] == 0) {
        printLCS2(x, i - 1, j - 1, temp);
        temp[count2++] = x[i - 1];
        // printf("%d ", x[i - 1]);
    } else if (b[i][j] == 1) {
        printLCS2(x, i - 1, j, temp);
    } else {
        printLCS2(x, i, j - 1, temp);
    }
}

/*
 * N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的 K位同学排成合唱队形。
 * 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，
 * 则他们的身高满足T1 < T2 < ...< Ti > Ti+1 > … > TK (1 <= i <= K)。
 * 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
 * Input
 * 输入包含若干个测试用例。
 * 对于每个测试用例，输入第一行是一个整数N(2<=N<=100)，表示同学的总数。
 * 第二行有N个整数，用空格分隔，第i个整数 Ti(130<=Ti<=230)是第i位同学的身高(厘米)。
 * 当输入同学总数N为0时表示输入结束。
 * Output
 * 对于每个测试案例，输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
 * Sample Input
 * 8
 * 186 186 150 200 160 130 197 220
 * 3
 * 150 130 140
 * 0
 * Sample Output
 * 4
 * 1
 * Hint
 * 合唱队形满足T1 < T2 < ...< Ti > Ti+1 > … > TK (1 <= i <= K),其中里面最具有指标性意义的人是Ti,
 * 由于(1 <= i <= K),意味着每个人都可能是作为中间的指标性人物,因此可枚举所有情况.
 * 对于每种情况,指标性人物往左应求一个最长的队列,往右也应求一最长的队列(当然此队列要包含指标人物本身).
 * 如下例:
 * 8个人
 *                               186 186 150  200 160 130 197 220
 * 以第i个人作为中心往左的最长序列：1    1   1   2   2    1   3  4
 * 以第i个人作为中心往右的最长序列：3    3   2   3   2    1   1  1
 *
 * 思路：
 * 求身高序列的最长递增（注意不是非递减）子序列和最长递减（注意不是递增）子序列
 * 然后两个序列合并即可以求出最长的合唱队形，然后就可以求出去除的人数了
 * 而最长递增和最长递减子序列时，可以先排序，再去除重复的，转为求最长公共子序列
 */
int main() {
    int i, j, result;
    while (scanf("%d", &n)) {
        m1 = n;
        m2 = n;
        if (n == 0) {
            break;
        }
        for (i = 0; i < n; i++) {
            scanf("%d", &normal[i]);
            decrease[i] = normal[i];
            increase[i] = normal[i];
        }
        //排序
        sort(increase, increase + n);
        sort(decrease, decrease + n, cmp);
        //去掉重复的数字，把重复的数字置最大值，排序后取前面的数
        for (i = 0, j = 1; i < n;) {
            if (increase[i] == increase[j]) {
                increase[i] = MAX;
                i = j;
                j++;
                m1--;
            } else {
                i++;
                j++;
            }
        }
        sort(increase, increase + n);
        //去掉重复的数字，把重复的数字置最小值，排序后取前面的数
        for (i = 0, j = 1; i < n;) {
            if (decrease[i] == decrease[j]) {
                decrease[i] = MIN;
                i = j;
                j++;
                m2--;
            } else {
                i++;
                j++;
            }
        }
        sort(decrease, decrease + n, cmp);
        //求最长递增子序列
        LCSLength(normal, increase, n, m1);
        count1 = 0;
        printLCS1(normal, n, m1, temp1);
        //        for (i = 0; i < count1; i++) {
        //            printf("%d ", temp1[i]);
        //        }
        //        printf("\n");
        memset(c, 0, sizeof (c));
        memset(b, 0, sizeof (b));
        //求最长递减子序列
        LCSLength(normal, decrease, n, m2);
        count2 = 0;
        printLCS2(normal, n, m2, temp2);
        //        for (i = 0; i < count2; i++) {
        //            printf("%d ", temp2[i]);
        //        }
        //        printf("\n");

        //合并两个最长递增和递减子序列，排成合唱队形
        for (i = count1 - 1, j = 0; i >= 0 && j < count2;) {
            if (temp1[i] > temp2[j]) {
                i--;
            } else if (temp1[i] < temp2[j]) {
                j++;
            } else {
                break;
            }
        }
        if (count1 == 0 || count2 == 0) {
            result = 0;
        } else if (i < 0 || j >= count2) {
            result = count1 > count2 ? count1 : count2;
            result = n - result;
        } else {
            result = n - (i + count2 - j);
            int tem = count1 > count2 ? count1 : count2;
            tem = n - tem;
            result = tem < result ? tem : result;
        }
        //输出去掉最少的人数
        printf("%d\n", result);
        memset(c, 0, sizeof (c));
        memset(b, 0, sizeof (b));
        memset(temp1, 0, sizeof (temp1));
        memset(temp2, 0, sizeof (temp2));
    }
    return 1;
}