zoj2136 && poj2533 Longest Ordered Subsequence ——最长上升子序列经典DP

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1136   http://poj.org/problem?id=2533 题目大意：RT 题目思路： 　　maxlen[j]表示，到j位置，最长的上升子序列的长度。时间复杂度O（N^2），数据范围是1000 　　参考解题报告：http://www.slyar.com/blog/longest-ordered-subsequence.html zoj:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int str[1000], maxlen[1001], p[1001];
int main(void){
#ifdef LOCAL
  freopen("lis.in", "r", stdin);
#endif
  int n, i, j, tmp, T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
      scanf("%d", str+i);
    }
    memset(maxlen, 0, sizeof(maxlen));
    maxlen[0] = 1;
    for (i = 1; i < n; ++i) {
      tmp = 0;
      for (j = 0; j < i; ++j) {
        if (str[j] < str[i]) {
          if (tmp < maxlen[j]) {
            tmp = maxlen[j];
          }
        }
      }
      maxlen[i] = tmp + 1;
    }
    tmp = -1;
    for (i = 0; i < n; ++i) {
      if (tmp < maxlen[i]) {
        tmp = maxlen[i];
      }
    }
    printf("%d\n", tmp);
    if (T) printf("\n");
  }

  return 0;
}

貌似有的时候zoj也会对

#ifndef ONLINE_JUDGE
  freopen(".in", "r", stdin);
#endif

报CE……所以，还是用#define LOCAL吧…… poj  

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int str[1000], maxlen[1001], p[1001];
int main(void){
#ifdef LOCAL
  freopen("lis.in", "r", stdin);
#endif
  int n, i, j, tmp, T;
//  scanf("%d", &T);
  //while (T--) 
  {
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
      scanf("%d", str+i);
    }
    memset(maxlen, 0, sizeof(maxlen));
    maxlen[0] = 1;
    for (i = 1; i < n; ++i) {
      tmp = 0;
      for (j = 0; j < i; ++j) {
        if (str[j] < str[i]) {
          if (tmp < maxlen[j]) {
            tmp = maxlen[j];
          }
        }
      }
      maxlen[i] = tmp + 1;
    }
    tmp = -1;
    for (i = 0; i < n; ++i) {
      if (tmp < maxlen[i]) {
        tmp = maxlen[i];
      }
    }
    printf("%d\n", tmp);
    //if (T) printf("\n");
  }

  return 0;
}

  貌似还有一种nlogn的方法：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
const int Size = 1009;
int Stack[Size];
void bin(int tmp, int top) {
  int low = 1, high = top, mid;
  while (low <= high) {
    mid = (high + low) / 2;
    if (tmp > Stack[mid]) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  Stack[low] = tmp;
}
int main(void){
#ifdef LOCAL
  freopen("2533.in", "r", stdin);
#endif
  int i, j, n, top, tmp;
  scanf("%d", &n);
  Stack[0] = -1; top = 0;
  for (i = 0; i < n; ++i) {
    scanf("%d", &tmp);
    if (tmp > Stack[top]) {
      Stack[++top] = tmp;
    } else {
      bin(tmp, top);
      /*
      int low = 1, high = top, mid;
      while (low <= high) {
        mid = (low + high) / 2;
        if (tmp > Stack[mid]) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      Stack[low] = tmp;
      */
    }
  }
  printf("%d\n", top);

  return 0;
}

这个方法虽然最终不能求出最长的上升子序列，但是可以求出最长上升子序列的长度。