(UVA) 1196 - Tiling Up Blocks

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=3637&mosmsg=Submission+received+with+ID+17773440

題目大意：
給你n個東西(1<=n<=10^4)，每個東西有a,b(1<=a,b<=100)值。當某個東西要裝在另外一個東西時，需要符合條件a1>=a2 且 b1>=b2。問說：最大疊中，有多少個。

基本上，先按照a值排序，a值相同，在比較b值(就是c++ pair的sort)，你就開個dp陣列，dp[i]記錄說是i為最後的有多少個。那對於當前的b，我們可以做出dp[b] = max(dp[1~b]) + 1。最後輸出dp陣列最大的即可。

複雜度：O (n*a)  //也可以dp那裏用segment tree壓到 O(n lg a)

#include <iostream>
#include <stdio.h>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 1e4+6;
const int MAX_M = 1e2+3;

pii v[MAX_N];
int dp[MAX_M];

int main () {
 int n;
 while (scanf("%d",&n) != EOF) {
  if (!n) {
   puts("*");
   return 0;
  }
  for (int x=0;n>x;x++){
   int i,j;
   scanf("%d %d",&i,&j);
   v[x]=make_pair(i,j);
  }
  sort(v,v+n);
  memset(dp,0,sizeof(dp));
  for (int x=0;n>x;x++){
   int i=0,j=v[x].second;
   for (int y=1;j>=y;y++) {
    i=max(i,dp[y]);
   }
   dp[j] = i + 1;
  }
  int ans=0;
  for (int x=1;MAX_M>x;x++) ans=max(ans,dp[x]);
  printf("%d\n",ans);
 }
}