UVa1255

UVa1255
ある時間からある時間までにどれくらいスタックに入れられるかメモ化orDP
memo[begin][end] = max{ 1 + memo[A][B] + memo[B][end] }

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " " << a << endl;

typedef long long int lli;

using namespace std;

const int N = 300 + 1;
pair<int, int> p[N];

const int M = N * 2;
int t[M];

int memo[M][M];

int rec(int ith, int begin, int end, int size)
{
  int &ret = memo[begin][end];
  if (ret != -1) return ret;

  int mx = 0;

  for (int i = ith; i < size; ++i) {
    int A = t[p[i].first];
    int B = t[p[i].second];

    if (t[begin] <= A && B <= t[end]) {
      int sum = 1;
      sum += rec(i + 1, p[i].first, p[i].second, size);
      sum += rec(i + 1, p[i].second, end, size);
      mx = max(mx, sum);
    }
  }

  return ret = mx;
}

bool cmp(pair<int, int> a, pair<int, int> b)
{
  if (t[a.first] != t[b.first]) return t[a.first] < t[b.first];
  return t[a.second] > t[b.second];
}

int main(int argc, char *argv[])
{
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    for (int i = 0, j = 0; i < n; ++i) {
      int a, b;
      cin >> t[a = j++];
      cin >> t[b = j++];
      p[i] = make_pair(a, b);
    }
    t[n * 2] = 0;
    t[n * 2 + 1] = 2000000000;
    sort(p, p + n, cmp);

    fill(&memo[0][0], &memo[M - 1][M], -1);
    cout << rec(0, n * 2, n * 2 + 1, n) << endl;
  }
  return 0;
}