T1 缤纷序列
题面
nodgd出了一道坑爹题但还没造数据，这道题的数据是一个长度为\(n\)的颜色序列，每个颜色都是红绿蓝三种颜色之一，且满足\(m\)个约束条件，每个条件都形如：第\(l_i\)到第\(r_i\)个颜色共有\(x_i\)种。请你计算共有多少种符合条件的颜色序列，答案\(\bmod 10^9+7\) 。
题解
本题是序列问题，多用dp解决,我们不妨设状态\(f[i][j][k]\)表示在当前位置i，除当前位置离i最近的不同颜色的位置为j,最后一种颜色离i最近的位置为j，则可以得出递推式
dp方程 :\(f[i][j][k]\) \(\begin{cases}f[i + 1][i][k](下一位置填j的颜色，将j覆盖掉) \\f[i + 1][i][j](下一位置填k的颜色，将k覆盖掉)\\f[i + 1][j][k](下一位置填i的颜色，不变)\end{cases}\)
时间复杂度\(O(n^3)\)。
在写代码时一定要注意要将\(i,j,k\)按大小依次枚举，这样既保证了后两位离i的距离前短后长，又方便枚举。\(i,j,k\)都可以取到0，可以使用\(j <= i - (i > 0)\)枚举0,最后如果\(i\)在限制区间的右端点上，暴力枚举，将不为\(x_i\)的状态赋值为0即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define R register
typedef long long ll;
const int Mod = 1e9 + 7;
const int MAXN = 3e2 + 5;
long long f[MAXN][MAXN][MAXN];
struct node
{
int l,r,v;
};
bool cmp(node a,node b)
{
return a.r < b.r;
}
node a[MAXN];
int main()
{
int n,m;
scanf("%d %d", &n, &m);
for(R int i = 1;i <= m; i++)
scanf("%d %d %d", &a[i].l, &a[i].r ,&a[i].v);
f[0][0][0] = 1;
sort(a + 1,a + 1 + m,cmp);
int cnt = 1;
for(R int i = 0;i < n;)
{
for(R int j = 0;j <= (i - (i > 0)); j++)
{
for(R int k = 0;k <= (j - (j > 0)); k++)
{
f[i + 1][j][k] = (f[i][j][k] + f[i + 1][j][k]) % Mod;
f[i + 1][i][j] = (f[i][j][k] + f[i + 1][i][j]) % Mod;
f[i + 1][i][k] = (f[i][j][k] + f[i + 1][i][k]) % Mod;
}
}
i++;
while(i == a[cnt].r)
{
if(a[cnt].v == 1)
{
for(R int j = a[cnt].l;j < i; j++)
for(R int k = 0;k <= (j - (j > 0)); k++)
f[i][j][k] = 0;
}
else if(a[cnt].v == 2)
{
for(R int j = a[cnt].l;j < i; j++)
for(R int k = a[cnt].l;k <= (j - (j > 0)); k++)
f[i][j][k] = 0;
for(R int j = 0;j < a[cnt].l; j++)
for(R int k = 0;k <= (j - (j > 0)); k++)
f[i][j][k] = 0;
}
else if(a[cnt].v == 3)
{
for(R int j = 0;j < a[cnt].l; j++)
for(R int k = 0;k <= (j - (j > 0)); k++)
f[i][j][k] = 0;
for(R int j = a[cnt].l;j < i; j++)
for(R int k = 0;k < a[cnt].l; k++)
f[i][j][k] = 0;
}
cnt++;
}
}
ll ans = 0;
for(R int i = 0;i <= n; i++)
for(R int j = 0;j <= (i - (i > 0)); j++)
ans = (ans + f[n][i][j]) % Mod;
printf("%lld", ans);
return 0;
}