正题

题目链接: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;

}

巴特西

AT2567-[ARC074C]RGB Sequence【dp】

正题

题目大意

解题思路

code

最新文章

热门文章