ARC074 E RGB Sequence DP

题解：

　　首先，有一个不太直观的状态，f[i][j][k][l]表示DP到i位，三种颜色最后出现的位置分别是j, k, l的方案数。因为知道了三种颜色最后出现的位置，因此也可以得知以当前点为右端点的区间内有几种颜色了，因为左端点不断向左扩张的时候，颜色数不会减少。

　　然后考虑优化这个状态，观察到因为每一位都必须有一个颜色，所以这3种颜色当中最后出现的那个所在的位置一定是当前的i。因此我们就可以去掉i，所以复杂度变成了$n^3$,就可以过此题了。

每次转移之前判断一下是否满足当前右端点的限制，如果不满足就continue，否则枚举颜色转移即可。

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 302

 #define ac 500

 #define mod 1000000007

 #define LL long long

 int n, m;

 int Head[AC], date[ac], Next[ac], len[ac], tot;

 LL f[AC][AC][AC], ans;

 inline int read()

 {

     int x = ;char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 inline void add(int f, int w, int S)

 {

     date[++tot] = w, Next[tot] = Head[f], Head[f] = tot, len[tot] = S;

 }

 inline void pre()

 {

     int a, b, c;

     n = read(), m = read();

     for(R i = ; i <= m; i ++)

     {

         a = read(), b = read(), c = read();

         add(b, a, c);//以右端点为标准

     }

 }

 inline int Max(int x, int y, int z)

 {

     if(y > x) x = y;

     if(z > x) x = z;

     return x;

 }

 inline bool check(int x, int y, int z)

 {

     if(x && y && x == y) return false;

     if(x && z && x == z) return false;

     if(y && z && y == z) return false;

     int k = Max(x, y, z);

     for(R i = Head[k]; i; i = Next[i])

     {

         int now = date[i], v = len[i], tmp = ;

         if(x >= now) ++ tmp;

         if(y >= now) ++ tmp;

         if(z >= now) ++ tmp;

         if(tmp != v) return false;

     }

     return true;

 }

 void work()

 {

     f[][][] = ;

     for(R i = ; i <= n; i ++)

         for(R j = ; j <= n; j ++)

             for(R l = ; l <= n; l ++)

             {

                 int k = Max(i, j, l);

                 if(!f[i][j][l]) continue;

                 //printf("(%d, %d, %d) = %lld\n", i, j, l, f[i][j][l]);

                 if(!check(i, j, l)) continue;

                 LL t = f[i][j][l];

                 f[k + ][j][l] = (f[k + ][j][l] + t) % mod;

                 f[i][k + ][l] = (f[i][k + ][l] + t) % mod;

                 f[i][j][k + ] = (f[i][j][k + ] + t) % mod;

                 if(k == n) ans = (ans + f[i][j][l]) % mod;//必须到排到了n

             }

     printf("%lld\n", ans);

 }

 int main()

 {

     freopen("in.in", "r", stdin);

     pre();

     work();

     fclose(stdin);

     return ;

 }

巴特西

ARC074 E RGB Sequence DP

最新文章

热门文章