最长双调序列

时间：2010-07-15 来源：jerryz920

计算最长双调序列……
这个算法还是可以继续优化的吧，应该是有O(NlnN)的算法，先考虑一下单调增序列的情况：扫描到元素时a[i]，只要找到一个可以扩展的最长序列即可，因为可以证明如果a[i]包含在最优子序列里，那么一定也包含这个子序列，这是最优子结构就不用多说了。唯一tricky的一点就是注意到长度为k的序列的最小末尾元素一定是比长度为k+1的序列的最小末尾元素小的，这个可以用归纳法证明
对于折线序列，也是一样的，无非就是个最长的递减序列了，同样可以binary search呀binary search~但是懒了，不写了，写binary search最容易出错了~额~

#include <stdio.h>
#include <stdlib.h>

template<class T>
static inline void checkMax(T& dst, T src) {
  if (src > dst) dst = src;
}

static int solve(int* h, int n)
{
  int* longest_up;
  int* longest_turn;

  longest_up = (int*) malloc(sizeof(int) * n);
  longest_turn = (int*) malloc(sizeof(int) * n);

  longest_up[0] = 1;
  for (int i = 1; i < n; i++) {
    longest_up[i] = 1;
    for (int j = 0; j < i; j++) {
      if (h[i] > h[j])
        checkMax(longest_up[i], longest_up[j] + 1);
    }
  }

  longest_turn[0] = 1;
  for (int i = 1; i < n; i++) {
    longest_turn[i] = 1;
    for (int j = 0; j < i; j++) {
      if (h[i] < h[j]) {
        checkMax(longest_turn[i], longest_turn[j] + 1);
        checkMax(longest_turn[i], longest_up[j] + 1);
      }
    }
  }
  int max_len = 0;
  for (int i = 0; i < n; i++) {
    checkMax(max_len, longest_turn[i]);
    checkMax(max_len, longest_up[i]);
  }
  free(longest_up);
  free(longest_turn);
  return n - max_len;
}

int main()
{
  int n;
  int h[300];
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    scanf("%d", &h[i]);
  printf("%d\n", solve(h, n));
}