[AtCoder2567]RGB Sequence

Posted on | In

先说几句题外话，这题是国家集训队作业

不过个人认为$AtCoder$上面的题质量真心不错

这题我硬是调了大半天，坑点还是有几个

而且这题竟然没有题解？？？赶紧过来水一发

这题正常人一眼过去就应该是$DP$，别告诉我你不是正常人

至于为什么显然是$DP$。。。方案数不是$DP$是什么？

因为颜色的数量很少，只有三种

所以可以直接上三维$DP$，话说这好像还是我第一道三维$DP$

所以我们可以用$f$ $[$ $i$ $]$ $[$ $j$ $]$ $[$ $k$ $]$来记录状态，统计方案数

$i$是当前枚举到的位置，$j$和$k$则分别是另外两种颜色最后出现的位置

建议将$j$设置为另外两种颜色靠后的那一种，枚举起来比较方便

然后思考状态转移方程，这里要分三种情况情况讨论

  • $i+1$位置上的颜色与$i$位置上的颜色一致

    那么显然$j$和$k$的位置不变，$f$ $[$ $i+1$ $]$ $[$ $j$ $]$ $[$ $k$ $]$ $=$ $f$ $[$ $i$ $]$ $[$ $j$ $]$ $[$ $k$ $]$

  • $i+1$位置上的颜色与$j$位置上的颜色一致

    那么$i$位置上的颜色就要后移一位，$f$ $[$ $i+1$ $]$ $[$ $i$ $]$ $[$ $k$ $]$ $=$ $f$ $[$ $i$ $]$ $[$ $j$ $]$ $[$ $k$ $]$

  • $i+1$位置上的颜色与$k$位置上的颜色一致

    那么$i$和$j$位置上的颜色都要后移一位，$f$ $[$ $i+1$ $]$ $[$ $i$ $]$ $[$ $j$ $]$ $=$ $f$ $[$ $i$ $]$ $[$ $j$ $]$ $[$ $k$ $]$

接下来我们以右端点为限制考虑贡献，这里脑补一下

根据$j$和$k$的大小关系判断区间内的颜色数量

不满足区间限制的直接赋值为0，不参与贡献

最后统计答案即可，这里要注意开$long$ $long$

因为之前只是统计了区间内颜色数量而不是统计颜色方案数

就是之前没有计算区间内具体有什么颜色

所以统计答案之后一定要将$ans$乘以$3$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int f[333][333][333];
int m,n,l,r,x,ans,size;
vector < pair < int , int > > rer[333];
inline void update(int &x,int y){ x=((long long)1*x+y+mod)%mod; }
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&l,&r,&x);
        rer[r].push_back(make_pair(l,x));
    }
    f[1][0][0]=1;
    for(register int i=1;i<=n;++i)
    {
        size=rer[i].size();
        for(register int j=0;j<size;++j)
        {
            l=rer[i][j].first;x=rer[i][j].second;
            for(register int k=0;k<i;++k)
                for(register int p=0;p<=max(0,k-1);++p)
                {
                    if(x==1) { if(l<=k) f[i][k][p]=0; }
                    else if(x==2) { if(k<l||l<=p) f[i][k][p]=0; }
                    else { if(p<l) f[i][k][p]=0; }
                }
        }
        if(i==n) break ;
        for(register int j=0;j<i;++j)
            for(register int k=0;k<=max(0,j-1);++k)
                if(!f[i][j][k]) continue ;
                else
                {
                    update(f[i+1][j][k],f[i][j][k]);
                    update(f[i+1][i][k],f[i][j][k]);
                    update(f[i+1][i][j],f[i][j][k]);
                }
    }
    for(register int j=0;j<n;++j)
        for(register int k=0;k<=max(0,j-1);++k)
            update(ans,f[n][j][k]);
    ans=((long long)3*ans)%mod;
    printf("%d\n",ans);
    return 0;
}