洛谷 P4099 SAO —— 树形dp

题目链接：点我啊╭(╯^╰)╮

题目大意：

    树形图，求拓扑序数量

解题思路：

    $dp[i][j]$ 为 $i$ 在子树中拓扑序排名为 $j$ 的方案数
    有 $dp[x][p1]$、$dp[y][p2]$，$x$ 为 $y$ 的父亲，得到新的 $dp[x][p3]$
    则 $x$ 原来排在 $p1$，更新为 $p3$，$y$ 原来排在 $p2$、更新为 $p4$
    问题在于 $p3$ 的范围，和怎么求方案数

---

    若 $x$ 的拓扑序在 $y$ 之前，则 $p3<p4$
    $p1$ 左边的一定在 $p3$ 左边，$p1$ 右边的一定在 $p3$ 右边，$p2$ 右边的一定在 $p3$ 右边
    而 $p2$ 左边的可以任意摆，则 $p1-1\le p3-1\le p1-1+p2-1$，得到 $p1\le p3\le p1+p2-1$

    左边有 $p3-1$ 个点，有 $p1-1$ 个一定来自 $x$ 的原序列，填坑的方案数为 $C_{p3-1}^{p1-1}$
    右边有 $s{z}_x+s{z}_y-p3$ 个点，有 $s{z}_x-p1$ 个点一定来自 $x$ 的原序列，填坑的方案数为 $C_{s{z}_x+s{z}_y-p3}^{s{z}_x-p1}$
    $dp[x][p3]+=C_{p3-1}^{p1-1}\times C_{s{z}_x+s{z}_y-p3}^{s{z}_x-p1}\times dp[x][p1]\times dp[y][p2]$
    转移是$n^3$的，代码如下：

for p1 in [1,sz_x]for p2 in [1,sz_y]for p3 in [p1,p1+p2-1]

    $p2$ 在转移式中只出现了一次，因此调换顺序后：

for p1 in [1,sz_x]for p3 in [p1,p1+sz_y-1]for p2 in [p3-p1+1,sz_y]

    前缀和优化即可，时间复杂度降为 $n^2$

---

    若 $x$ 的拓扑序在 $y$ 之后，则 $p3>p4$
    $p1+p2\le p3\le p1+szx$，原来的转移式如下：

for p1 in [1,sz_x]for p2 in [1,sz_y]for p3 in [p1+p2,p1+sz_x]

    调换顺序后如下：

for p1 in [1,sz_x]for p3 in [p1+1,p1+sz_x]for p2 in [1,p3-p1]

---

#include<bits/stdc++.h> #define rint register int #define deb(x) cerr<<#x<<" = "<<(x)<<'\n'; using namespace std; typedef long long ll; using pii = pair <int,int>; const int maxn = 1e3 + 5; const ll mod = 1e9 + 7; int T, n, a[maxn][maxn], sz[maxn]; ll dp[maxn][maxn], C[maxn][maxn]; ll f[maxn], sum[maxn][maxn]; vector <int> g[maxn];void dfs(int u, int fa) {sz[u] = 1, dp[u][1] = 1;for(auto v : g[u]) {if(sz[v]) continue;dfs(v, u);for(int i=1; i<=sz[u]; i++) f[i] = dp[u][i];memset(dp[u], 0, sizeof(dp[u]));for(int i=1; i<=sz[v]; i++) sum[v][i] = (sum[v][i-1] + dp[v][i]) % mod;if(a[u][v])for(int i=1; i<=sz[u]; i++)for(int k=i; k<=i+sz[v]-1; k++) // for(int j=k-i+1; j<=sz[v]; j++)(dp[u][k] += C[k-1][i-1] * C[sz[u]+sz[v]-k][sz[u]-i] % mod * f[i]\% mod * (sum[v][sz[v]] - sum[v][k-i] + mod) % mod) %= mod;else for(int i=1; i<=sz[u]; i++)for(int k=i+1; k<=i+sz[v]; k++) // for(int j=1; j<=k-i; j++)(dp[u][k] += C[k-1][i-1] * C[sz[u]+sz[v]-k][sz[u]-i] % mod * f[i]\% mod * sum[v][k-i] % mod) %= mod;sz[u] += sz[v];} }int main() {for(int i=0; i<=1e3; i++) C[i][0] = 1;for(int i=1; i<=1e3; i++)for(int j=1; j<=i; j++)C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;scanf("%d", &T);while(T--) {char str;scanf("%d", &n);memset(a, 0, sizeof(a));memset(sz, 0, sizeof(sz));memset(dp, 0, sizeof(dp));for(int i=1; i<=n; i++) g[i].clear();for(int i=1, x, y; i<n; i++) {scanf("%d %c %d", &x, &str, &y);x++, y++;if(str == '<') a[x][y] = 1;else a[y][x] = 1;g[x].push_back(y);g[y].push_back(x);}dfs(1, 0);ll ans = 0;for(int i=1; i<=n; i++) ans = (ans + dp[1][i]) % mod;printf("%lld\n", ans);} }

总结

以上是生活随笔为你收集整理的洛谷 P4099 SAO —— 树形dp的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。