Codeforces 1152D - Neko and Aki's Prank (dp)
题意
求由所有长度为 2n的合法括号匹配序列组成字典树的二分图最大匹配(给边染色是的染色的边没有交点)
做法
考虑树形 dp(可能不是?).
dp[i][j][0/1]表示当前节点已经有 i个左括号, j个右括号, 且改节点与父亲节点的边是否染色 (0/1)的方案数
则有转移方程:
dp[i][j][0]=dp[i][j−1][1](j>i)+dp[i−1][j][1]
dp[i][j][1]=max(dp[i−1][j][0]+1+dp[i][j−1][1],dp[i−1][j][1]+1+dp[i][j−1][0])
答案为 dp[n][n][1], 总状态数 O(n2), 转移 O(1), 总复杂度 O(n2).
但由于转移涉及到大小比较,所以需要用大数,实际不用大数也能过,不知道原因(可能 dp[i][j][0]与 dp[i][j][1]比较接近,而且没有等于1e9+7的情况)
代码
python3太慢(提速技巧: 交pypy3(可提速3倍),尽量少开多维数组,少定义局部变量)
n = int(input())
f = [[0]*(n+1) for i in range(n+1)]
g = [[0]*(n+1) for i in range(n+1)]
mod = 10**9+7
for i in range(1, n + 1):
f[0][i] = g[0][i - 1]
g[0][i] = f[0][i - 1] + 1
t = [0, 0]
for i in range(1, n + 1):
for j in range(i, n + 1):
if i > 0:
f[i][j] += g[i - 1][j]
t[0] = g[i - 1][j]
t[1] = f[i - 1][j] + 1
if j > i:
f[i][j] += g[i][j-1]
t[0] += f[i][j - 1] + 1
t[1] += g[i][j - 1]
for k in t: g[i][j] = max(g[i][j], k)
print(g[n][n]%mod)