題目鏈接：點我啊╭(╯^╰)╮

題目大意：

????樹形圖，求拓撲序數量

解題思路：

????$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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。