arc074e

题意：用三种颜色染一个长度为n的序列，m个条件，每个条件为一段区间内的颜色个数为x。求满足条件的序列个数。

设$$f[i][j][k]$$表示到$$i$$,最后出现位置最靠前的颜色最后出现位置为$$k$$，最后出现位置第二靠前的颜色最后出现位置为$$j$$的方案数。

#include <bits/stdc++.h>
using namespace std;
#define PA pair<int,int>
const int N=310,mod=1000000007;
int n,m,ans;
struct node
{
    int l,r,num;
    friend bool operator < (const node &r1,const node &r2)
    {return r1.r<r2.r;}
}a[N];
int f[N][N][N];
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].num);
    sort(a+1,a+1+m);
    f[1][0][0]=3;
    for(int i=1,now=1;i<=n;i++)
    {
        while(now<=m&&a[now].r==i)
        {
            int l=a[now].l,num=a[now].num;
            for(int j=0;j<i;j++)
                for(int k=0;k<=j;k++)
                {
                    int t=1;
                    if(j>=l)t++;
                    if(k>=l)t++;
                    if(t!=num)f[i][j][k]=0;
                }
            now++;
        }
        if(i==n)break;
        for(int j=0;j<i;j++)
            for(int k=0;k<=j;k++)
            {
                (f[i+1][j][k]+=f[i][j][k])%=mod;
                (f[i+1][i][k]+=f[i][j][k])%=mod;
                (f[i+1][i][j]+=f[i][j][k])%=mod;
            }
    }
    for(int j=0;j<n;j++)
        for(int k=0;k<=j;k++)
            (ans+=f[n][j][k])%=mod;
    printf("%d\n",ans);
    return 0;
}