# ARC 074 E - RGB Sequence ( DP )

E: RGB Sequence - AtCoder Regular Contest 074 | AtCoder

N 個格子一排。

M 條限制，表示 [ L, R ] 中要有 X 種顏色。

1≤N≤300
1≤M≤300
1≤li≤ri≤N
1≤xi≤3

dp[ i ][ j ][ k ]：第 { 1, 2, 3 } 種顏色最後出現的位置 { i, j, k }，此時的方案數。

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;
}
```