AT2567-[ARC074C]RGB Sequence【dp】

正題

題目連結:https://www.luogu.com.cn/problem/AT2567

題目大意

長度為\(n\)的包含三種顔色\(RGB\)的序列，\(m\)個限制\([l,r,k]\)表示區間\(l\sim r\)恰好有\(k\)種顔色。

求方案數

\(1\leq n\leq 300\)

解題思路

很水的題是吧，設\(f_{i,j,k}\)表示最近三種顔色出現位置依次是\(i,j,k(i>j>k)\)（不需要考慮這個三個位置具體的顔色，隻需要用這些位置的顔色不同這一資訊）

然後每次\(dp\)完到右端點把不合法的判掉就好了。

時間複雜度\(O(n^3+mn^2)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define mp(x,y) make_pair(x,y)
#define ll long long
using namespace std;
const ll N=310,P=1e9+7;
ll n,m,f[N][N][N],ans;
vector<pair<ll,ll> >q[N];
signed main()
{
	scanf("%lld%lld",&n,&m);n+=2;
	for(ll i=1;i<=m;i++){
		ll l,r,k;
		scanf("%lld%lld%lld",&l,&r,&k);
		l+=2;r+=2;q[r].push_back(mp(l,k));
	} 
	f[2][1][0]=1;
	for(ll i=3;i<=n;i++){
		for(ll j=1;j<i;j++)
			for(ll k=0;k<j;k++){
				(f[i][i-1][j]+=f[i-1][j][k])%=P;
				(f[i][i-1][k]+=f[i-1][j][k])%=P;
				(f[i][j][k]+=f[i-1][j][k])%=P;
			}
		for(ll z=0;z<q[i].size();z++){
			ll l=q[i][z].first,w=q[i][z].second;
			for(ll j=1;j<i;j++)
				for(ll k=0;k<j;k++)
					if(1+(j>=l)+(k>=l)!=w)f[i][j][k]=0;
		}
	}
	for(ll i=1;i<n;i++)
		for(ll j=0;j<i;j++)
			(ans+=f[n][i][j])%=P;
	printf("%lld\n",ans);
	return 0;
}