杭电多校Day1 T1官方题解

2019-07-22

四维DP？！

Blank

定义 $ dp[i][j][k][t] $ 代表填完前 $ t $ 个位置后， $ \begin{Bmatrix} 0,1,2,3 \end{Bmatrix} $ 这4个数字最后一次出现的位置，
排序后为 $ i,j,k,t ( i < j < k < t ) $ 的方案数目，则按照第 $ t+1 $ 位的数字的四种选择，可以得到四种转移。

对于限制可以按照限制区间的右端点分类，求出 $ dp [ i ] [ j ] [ k ] [ t ] $ 后，找到所有以 $ t $ 为区间右端点的限制条件，如果当前状态不满足所有限制条件则不合法，不再向后转移。

总时间复杂度 $ O(n^4) $ 。滚动一维，空间复杂度 $ O(n^3) $

UPD 一开始的模数为$10^9+7$，后来统一改成了$998244353$，但最后在polygon上生成数据的时候标程放错了，就跑出了模$10^9+7$的结果。对被这道题卡了的大佬们表示歉意！

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

typedef pair<int, int> piir;

const int N = 100 + 5;

int n, m, ans;

int dp[2][N][N][N];

vector <piir> lims[N];

inline void Mod(int &x) {
    static int mod = 998244353;//1e9 + 7;
    if (x >= mod) x -= mod;
}

int main() {
	int Case, ans, l, r, x;
    int i, j, k, t, p;
    for (scanf("%d", &Case); Case --; ) {
        ans = 0;
        scanf("%d %d", &n, &m);
        for (i = 1; i <= n; i ++)
            lims[i].clear();
        for (i = 0; i < m; i ++) {
            scanf("%d %d %d", &l, &r, &x);
            lims[r].push_back(piir(l, x));
        }
        dp[0][0][0][0] = 1;
        for (i = p = 1; i <= n; i ++, p ^= 1) {
        	for (j = 0; j <= i; j ++)
                for (k = 0; k <= j; k ++)
                    for (t = 0; t <= k; t ++)
            			dp[p][j][k][t] = 0;
            for (j = 0; j < i; j ++)
                for (k = 0; k <= j; k ++)
                    for (t = 0; t <= k; t ++) {
                        Mod(dp[p][j][k][t] += dp[p ^ 1][j][k][t]);
                        Mod(dp[p][i - 1][k][t] += dp[p ^ 1][j][k][t]);
                        Mod(dp[p][i - 1][j][t] += dp[p ^ 1][j][k][t]);
                        Mod(dp[p][i - 1][j][k] += dp[p ^ 1][j][k][t]);
                    }
            for (j = 0; j < i; j ++)
                for (k = 0; k <= j; k ++)
                    for (t = 0; t <= k; t ++)
                        for (piir tmp : lims[i])
                            if (1 + (j >= tmp.first) + (k >= tmp.first) + (t >= tmp.first) != tmp.second)
                                dp[p][j][k][t] = 0;
        }
        for (i = 0, p = n & 1; i < n; i ++)
            for (j = 0; j <= i; j ++)
                for (k = 0; k <= j; k ++)
                    Mod(ans += dp[p][i][j][k]);
        printf("%d\n", ans);
    }
    return 0;
}