ARC 074 E - RGB Sequence ( DP )

E: RGB Sequence - AtCoder Regular Contest 074 | AtCoder

題意：
N 個格子一排。
有三種顏色可以塗。
M 條限制，表示 [ L, R ] 中要有 X 種顏色。
求方案數模 1e9 + 7。

制約：
1≤N≤300
1≤M≤300
1≤li≤ri≤N
1≤xi≤3

解法：
dp[ i ][ j ][ k ]：第 { 1, 2, 3 } 種顏色最後出現的位置 { i, j, k }，此時的方案數。
有這狀態就能知道合不合限制。當 max{ i, j, k } 和某個限制的 R 一致的時候檢查。

複雜度：
O( N ** 3 + N ** 2 * M )

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = int( 1e9 ) + 7;
 
const int MAXN = 300;
const int MAXM = 300;
 
int N, M;
int L[ MAXM ], R[ MAXM ], X[ MAXM ];
vector< pair< int, int > > r2lx[ MAXN + 1 ];
 
int dp[ MAXN + 1 ][ MAXN + 1 ][ MAXN + 1 ];
 
signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < M; ++i ) {
    cin >> L[ i ] >> R[ i ] >> X[ i ];
    r2lx[ R[ i ] ].emplace_back( L[ i ], X[ i ] );
  }
  dp[ 0 ][ 0 ][ 0 ] = 1;
  for( int i = 0; i <= N; ++i ) {
    for( int j = 0; j <= N; ++j ) {
      for( int k = 0; k <= N; ++k ) {
        for( auto lx: r2lx[ max( { i, j, k } ) ] ) {
          int l, x; tie( l, x ) = lx;
          if( ( l <= i ) + ( l <= j ) + ( l <= k ) != x ) {
            dp[ i ][ j ][ k ] = 0;
          }
        }
        if( max( { i, j, k } ) == N ) continue;
        if( dp[ i ][ j ][ k ] == 0 ) continue;
        ( dp[ max( { i, j, k } ) + 1 ][ j ][ k ] += dp[ i ][ j ][ k ] ) %= MOD;
        ( dp[ i ][ max( { i, j, k } ) + 1 ][ k ] += dp[ i ][ j ][ k ] ) %= MOD;
        ( dp[ i ][ j ][ max( { i, j, k } ) + 1 ] += dp[ i ][ j ][ k ] ) %= MOD;
      }
    }
  }
  int ans = 0;
  for( int i = 0; i < N; ++i ) {
    for( int j = 0; j < N; ++j ) {
      ( ans += dp[ N ][ i ][ j ] ) %= MOD;
      ( ans += dp[ i ][ N ][ j ] ) %= MOD;
      ( ans += dp[ i ][ j ][ N ] ) %= MOD;
    }
  }
  cout << ans << endl;
  return 0;
}