练习题 - 合唱队形(最长下降子序列)

前言

算法拾遗继续。

题目

问题描述

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

输入(chorus.in)

输入文件chorus.in的第一行是一个整数N(2<=N<=100),表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

输出(chorus.out)

输出文件chorus.out包括一行,这一行只包含一个整数,就是最少需要几位同学出列。

样例

chorus.in

8
186 186 150 200 160 130 197 220

chorus.out

4

数据规模

对于50%的数据,保证有n<=20;
对于全部的数据,保证有n<=100。

解答

本题的解答思路可以为,依次以队列中的人为最高点,然后在左右两边的人中分别寻找最长上升子序列或者最长下降子序列即可求解。

具体代码实现如下。

#include <stdio.h>
#define MAX 100

FILE *in, *out;
int n, a[100], b[100], min = MAX;

void sweepb() {
  int i;
  for (i = 0; i <= n; i++)
    b[i] = 0;
}

int jiang(int x, int y, int num) {
  int k, end = 0, i, j, t, tem = x;

  if (x > y)
    return (0);

  if (x == y) {
    if (a[x] < num)
      return (0);
    else
      return (1);
  } else {
    while (a[x] >= num && x <= y)
      x++;

    if (x > y) {
      return (y - tem + 1); // in this case, all people at right side should leave
    } else {
      sweepb();

      b[1] = a[x];
      end = 1;
      for (k = x + 1; k <= y; k++) {
        if (a[k] >= num) {
          continue;
        } else {
          i = 1;
          j = end;
          t = (i + j) / 2;
          while (j - i > 1) {
            if (a[k] >= b[t]) {
              j = t;
              t = (i + j) / 2;
            } else {
              i = t;
              t = (i + j) / 2;
            }
          }
          if (a[k] >= b[i]) {
            b[i] = a[k];
          } else if (a[k] >= b[j]) {
            b[j] = a[k];
          } else {
            b[++end] = a[k];
          }
        } // end else
      } // end for
      return (y - tem + 1 - end); // in which case, end-many people at right side can stay
    } // end else
  } // end else
}

int shen(int x, int y, int num) {
  int k, end = 0, i, j, t, tem = x;
  if (x > y)
    return (0);
  if (x == y) {
    if (a[x] < num)
      return (0);
    else
      return (1);
  } else // else1
  {
    while (a[x] >= num && x <= y)
      x++;
    if (x > y)
      return (y - tem + 1);
    else // esls2
    {
      sweepb();
      b[1] = a[x];
      end = 1;
      for (k = x + 1; k <= y; k++) {
        if (a[k] >= num)
          continue;
        else // else 3
        {
          i = 1;
          j = end;
          t = (i + j) / 2;
          while (j - i > 1) {
            if (a[k] <= b[t]) {
              j = t;
              t = (i + j) / 2;
            } else {
              i = t;
              t = (i + j) / 2;
            }
          }
          if (a[k] <= b[i])
            b[i] = a[k];
          else if (a[k] <= b[j])
            b[j] = a[k];
          else
            b[++end] = a[k];
        } // end else 3
      } // end for
      return (y - tem + 1 - end);
    } // end else2
  } // end else1
} // end shen

int main() {
  int i, tem;

  in = fopen("chorus.in", "r");
  fscanf(in, "%d", &n);
  for (i = 0; i < n; i++)
    fscanf(in, "%d", &a[i]);
  fclose(in);

  for (i = 0; i < n; i++) {
    tem = jiang(i + 1, n - 1, a[i]) + shen(0, i - 1, a[i]);
    if (min > tem)
      min = tem;
  }

  out = fopen("chorus.out", "w");
  fprintf(out, "%d\n", min);
  fclose(out);

  return 0;
}

参考


* cached version, generated at 2018-12-02 20:29:53 UTC.

Subscribe by RSS