[URAL1526] Martian Plates

1个月前发布

Solution

算法标签️：括号序列、动态规划

根据题目所说的过程，不难抽象出相当于模拟栈的过程。其中，bringing dishes 相当于加入栈，taking away plates 相当于退出栈。于是，只需要对有限制条件的栈操作计数即可。

但是，会发现这样极其的难处理，需要维护各种信息（顺序、个数……），总之复杂度爆炸了。于是，考虑将栈转化成合法括号序列，这两者是一一对应的。在本题中，合法括号序列的含义是左括号是 bringing dishes，右括号是 taking away plates。而合法括号序列计数有两种求解方式：

区间 DP
线性 DP

其中，线性 DP 与栈的思考方式是相同的，舍去。于是，考虑区间 DP 这种方式。每个佳肴加入的时候，盘子还未端走等价于包含它的括号对，而区间 DP 的时候只需要将包含它的括号对加入状态即可（区间 DP 本质上就是在利用包含关系 DP，所以是好维护的）。注意到，没必要记录左右端点直接维护长度即可。令 \(f_{i,j}\) 表示长度为 \(i\) 的区间，包含它的状态为 \(j\) 的方案数，转移分为两种情况：

\((A)\)：枚举括号对对应着的菜品编号，并判断是否可以加入（给定的条件限制）。若可以，则 \(f_{i,j}\leftarrow f_{i-2,j\ \cup\ k}\)。
\(AB\)：枚举两个括号序列的分割点（注意️：这里容易算重，需要强制分割点左侧的括号序列必须是 \(1\) 类型的，若还是 \(2\) 类型则会在前面算过。），强制钦定左侧括号序列是 \(1\) 类型，也就是实际上计算的是 \((A)B\) 类型。只需要枚举括号对对应着的菜品编号，并判断是否可以加入。若可以，则 \(f_{i,j}\leftarrow f_{k-2,j\ \cup\ x}\times f_{i-k,j}\)。

时间复杂度：\(O(t^2 n2^n)\)。

Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int p, t, n, m;
int bad[10], dp[205][1 << 10];

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> p >> t >> n >> m;
	while (m -- ) {
		int u, v;
		cin >> u >> v;
		u --, v --;
		bad[v] |= 1 << u;
	}

	for (int i = 0; i < 1 << n; i ++) dp[0][i] = 1;
	for (int i = 2; i <= t; i += 2)
		for (int j = 0; j < 1 << n; j ++) {
			for (int k = 0; k < n; k ++)
				if ((bad[k] & j) == 0)
					(dp[i][j] += dp[i - 2][j | (1 << k)]) %= p;
			for (int k = 2; k < i; k += 2)
				for (int ch = 0; ch < n; ch ++)
					if ((bad[ch] & j) == 0)
						(dp[i][j] += dp[k - 2][j | (1 << ch)] * dp[i - k][j] % p) %= p;
		}

	cout << dp[t][0] << endl;

	return 0;
}