http://arc074.contest.atcoder.jp/tasks/arc074_c
ひたすらdp[i][j][k](i番目まで見たときRがj個あり、Gがk個ある場合の数)みたいな感じでやろうとしたけど、区間内にRGBがそれぞれ存在するかどうかだけわかればいいのでどう見ても情報を持ちすぎていた。
dp[i][j][k](Rを最後に使ったのがi番目、Gを最後に使ったのがj番目、Bを最後に使ったのがK番目の場合の数)でやるとうまくいく。
int N, M; ll dp[MAX_N][MAX_N][MAX_N]; vector<pi> I[MAX_N]; bool ok(int i, int j, int k) { int m = max(max(i, j), k); int size = (int)I[m].size(); for(int l = size - 1; l >= 0; l--) { int cnt = 0; pi p = I[m][l]; if(p.fst <= i) cnt++; if(p.fst <= j) cnt++; if(p.fst <= k) cnt++; if(cnt != p.sec) return false; } return true; } void solve() { cin >> N >> M; rep(i, 0, M) { int a, b, c; cin >> a >> b >> c; I[b].push_back(pi(a, c)); } rep(i, 0, N + 1) sort(all(I[i])); dp[0][0][0] = 1; rep(i, 0, N + 1) { rep(j, 0, N + 1) { rep(k, 0, N + 1) { int l = max(max(i, j), k); if(ok(i, j, l + 1)) ADD(dp[i][j][l + 1], dp[i][j][k]); if(ok(i, l + 1, k)) ADD(dp[i][l + 1][k], dp[i][j][k]); if(ok(l + 1, j, k)) ADD(dp[l + 1][j][k], dp[i][j][k]); } } } ll res = 0; rep(i, 0, N + 1) { rep(j, 0, N + 1) { rep(k, 0, N + 1) { if(max(max(i, j), k) == N) ADD(res, dp[i][j][k]); } } } cout << res << "\n"; }