2019HDU多校第一场 BLANK DP

题意：有四种数字，现在有若干个限制条件：每个区间中不同的数字种类必须是多少种，问合法的方案数。

思路：定义 dp[i][j][k][t] 代表填完前 t 个位置后，{0,1,2,3} 这 4 个数字最后一次出现的位置，排序后为 i,j,k,t(i < j < k < t) 的方案数目，则按照第 t+1 位的数字的四种选择，可以得到四种转移。对于限制可以按照限制区间的右端点分类，求出 dp[i][j][k][t] 后，找到所有以 t 为区间右端点的限制条件，如果当前状态不满足所有限制条件则不合法，不再向后转移。总时间复杂度 O(n4)。滚动一维，空间复杂度 O(n3)

代码：

#include <bits/stdc++.h>

#define pii pair<int, int>

using namespace std;

const int maxn = 101;

const int mod = 998244353;

int dp[2][maxn][maxn][maxn];

vector<pii> re[maxn];

int main() {

	int T, x, y, z, n, m;

	scanf("%d", &T);

	while(T--) {

		scanf("%d%d", &n, &m);

		for (int i = 1; i <= n; i++)

			re[i].clear();

		for (int i = 1; i <= n; i++)

			re[i].clear();

		for (int i = 1; i <= m; i++) {

			scanf("%d%d%d", &x, &y, &z);

			re[y].push_back(make_pair(x, z));

		}

		for (int i = 0; i < 2; i++) {

			for (int j = 0; j <= n; j++)

				for (int k = 0; k <= n; k++)

					for (int t = 0; t <= n; t++)

						dp[i][j][k][t] = 0;

		}

		for (int j = 0; j <= n; j++)

			for (int k = 0; k <= j; k++)

				for (int t = 0; t <= k; t++)

					dp[0][j][k][t] = 0;

		dp[0][0][0][0] = 1;

		for (int i = 1; i <= n; i++) {

			for (int j = 0; j <= i; j++)

				for (int k = 0; k <= j; k++)

					for (int t = 0; t <= k; t++)

						dp[i & 1][j][k][t] = 0;

			for (int j = 0; j <= i; j++)

				for (int k = 0; k <= j; k++)

					for (int t = 0; t <= k; t++) {

						int p = (i & 1) ^ 1;

						dp[i & 1][j][k][t] = (dp[i & 1][j][k][t] + dp[p][j][k][t]) % mod;

						dp[i & 1][i - 1][k][t] = (dp[i & 1][i - 1][k][t] + dp[p][j][k][t]) % mod;

						dp[i & 1][i - 1][j][t] = (dp[i & 1][i - 1][j][t] + dp[p][j][k][t]) % mod;

						dp[i & 1][i - 1][j][k] = (dp[i & 1][i - 1][j][k] + dp[p][j][k][t]) % mod;

					}

			for (int j = 0; j <= i; j++)

				for (int k = 0; k <= j; k++)

					for (int t = 0; t <= k; t++) {

						for (int t1 = 0; t1 < re[i].size(); t1++) {

							if(1 + (j >= re[i][t1].first) + (k >= re[i][t1].first) + (t >= re[i][t1].first) != re[i][t1].second) {

								dp[i & 1][j][k][t] = 0;

							}

						}

					}

		}

		int ans = 0;

		for (int i = 0; i <= n; i++)

			for (int j = 0; j <= i; j++)

				for (int k = 0; k <= j; k++)

					ans = (ans + dp[n & 1][i][j][k]) % mod;

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

	}

}

巴特西

2019HDU多校第一场 BLANK DP

最新文章

热门文章