【ARC074E】RGB Sequence（神奇的dp）

注意到颜色的种类数只有 \(3\) 种，\(n\leq 100\) 也很小。

然后就有了一种神奇的 dp 状态：

考虑从前往后填方块，设 \(dp(i,j,k)\) 表示离当前位置最近的颜色位置在 \(i\)，离当前位置第二近的颜色位置在 \(j\)，离当前位置第三近的颜色位置在 \(k\)。显然，当前位置就是 \(i\)，所以这样设置帮我们减少了一维。

先 \(O(n^2m)\) 枚举每一个区间和每一个要求，预处理哪些方案是不合法的，然后直接 \(O(n^3)\) 进行 dp 即可。

代码如下：

#include<bits/stdc++.h>
 
#define N 310
#define mod 1000000007
 
using namespace std;
 
int n,m,ql[N],qr[N],x[N];
int dp[N][N][N];
 
void add(int &x,int y)
{
    if((x+=y)>=mod) x-=mod;
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&ql[i],&qr[i],&x[i]);
    dp[1][0][0]=3;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<qr[i];j++)
        {
            int t=max(0,j-1);
            for(int k=0;k<=t;k++)
            {
                if(x[i]==1&&ql[i]<=j) dp[qr[i]][j][k]=-1;
                if(x[i]==2&&(j<ql[i]||ql[i]<=k)) dp[qr[i]][j][k]=-1;
                if(x[i]==3&&k<ql[i]) dp[qr[i]][j][k]=-1;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            int t=max(0,j-1);
            for(int k=0;k<=t;k++)
            {
                if(dp[i][j][k]==-1) continue;
                if(dp[i+1][j][k]!=-1) add(dp[i+1][j][k],dp[i][j][k]);
                if(dp[i+1][i][j]!=-1) add(dp[i+1][i][j],dp[i][j][k]);
                if(dp[i+1][i][k]!=-1) add(dp[i+1][i][k],dp[i][j][k]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int t=max(0,i-1);
        for(int j=0;j<=t;j++)
            if(dp[n][i][j]!=-1) 
                add(ans,dp[n][i][j]);
    }
    printf("%d\n",ans);
    return 0;
}