SRM578 Div1 Medium

500
http://community.topcoder.com/stat?c=problem_statement&pm=12534&rd=15498

memo[前の前に配置した地点][前に配置した地点]
ある２点間が、ある1つの区間に含まれるかどうかを前もって作っておく。
あとは、今現在着目している地点をこれまで配置した2点と同様の区間にならない様に選んでいく。

const int V = 300 + 10;
bool inc[V][V];
bool w[V];

const lli mod = 1000000007;
lli memo[V][V];

const int dummy = V - 1;
lli rec(int a, int b, int N)
{
  lli& ret = memo[a][b];
  if (ret != -1) return ret;
  lli sum = 1;
  const int begin = max((a == dummy ? 0 : a + 1), (b == dummy ? 0 : b + 1));
  const int end = N - 1;
  for (int c = begin; c <= end; ++c) {
    if (inc[a][c]) continue;
    sum += rec(b, c, N);
    sum %= mod;
  }
  return ret = sum;
}

class WolfInZooDivOne {
public:
  int count(int N, vector <string> L_, vector <string> R_)
  {
    const string L = accumulate(L_.begin(), L_.end(), string(""));
    const string R = accumulate(R_.begin(), R_.end(), string(""));

    vector< pair<int, int> > v;
    {
      istringstream issL(L);
      istringstream issR(R);
      int l, r;
      while ((issL >> l) && (issR >> r)) {
        v.push_back(make_pair(l, r));
      }
    }

    fill(&inc[0][0], &inc[V - 1][V - 1] + 1, false);
    for (int i = 0; i < N; ++i) {
      for (int j = i; j < N; ++j) {
        for (int k = 0; k < v.size(); ++k) {
          if (v[k].first <= i && j <= v[k].second) {
            inc[i][j] = true;
          }
        }
      }
    }

    fill(&memo[0][0], &memo[V - 1][V - 1] + 1, -1);
    return rec(dummy, dummy, N);
  }