problem

luogu-P3757

solution

$\text{observation}:$ $h_{i/2}?h_i$ 的大小關系，其實就是個二叉樹的大小關系。

這很類似之前的排列 $dp$ ，遷移過來，我們嘗試 $f(i,j):i$ 在子樹內第 $j$ 小的方案數。

當所有符號都是一個方向的時候，就是 [ZJOI2010]排列計數的題解，所以我們類比這里應該也是有組合數計算轉移的。

同樣是編號劃分離散化的理解。

假設當前點為 $u$，兒子為 $v$，枚舉 $u$ 為其所在連通塊的第 $i$ 小，$v$ 為其所在聯通塊的第 $j$ 小：

• $h_u<h_v$。

  考慮合并后，$u$ 可能在新大小為 $si{z}_u+si{z}_v$ 的連通塊中的排名。

  這就要看 $v$ 所在聯通塊前 $j$ 小的數與 $h_u$ 的關系了。

  但一定不會到 $i+j$。

  所以，枚舉合并后 $u$ 的排名為 $k$，$i\le k<i+j$。

  $f(u,k)\leftarrow f(u,i)?f(v,j)?\left(\genfrac{}{}{0ex}{}{k?1}{i?1}\right)?\left(\genfrac{}{}{0ex}{}{si{z}_u+si{z}_v?k}{si{z}_u?i}\right)$

• $h_u>h_v$。

  轉移方程式和原理同上一種情況，只是 $k$ 的范圍有所變化，$i+j\le k\le i+si{z}_v$。

時間復雜度為 $O(n^3)$。

前綴和優化 $O(n^2)$ 可以看[HEOI2013]SAO的題解。

code

#include <bits/stdc++.h> using namespace std; #define int long long #define mod 1000000007 #define maxn 105 char s[maxn]; int n; int c[maxn][maxn], f[maxn][maxn], g[maxn], siz[maxn];void dfs( int u ) {f[u][1] = siz[u] = 1;for( int o = 0;o <= 1;o ++ ) {int v = (u << 1) + o;if( v > n ) break;dfs( v );memcpy( g, f[u], sizeof( f[u] ) );memset( f[u], 0, sizeof( f[u] ) );for( int i = 1;i <= siz[u];i ++ )for( int j = 1;j <= siz[v];j ++ )if( s[v] == '>' ) {for( int k = i + j;k <= i + siz[v];k ++ )(f[u][k] += g[i] * c[k - 1][i - 1] % mod * f[v][j] % mod * c[siz[u] + siz[v] - k][siz[u] - i]) %= mod;}else {for( int k = i;k < i + j;k ++ )(f[u][k] += g[i] * c[k - 1][i - 1] % mod * f[v][j] % mod * c[siz[u] + siz[v] - k][siz[u] - i]) %= mod;}siz[u] += siz[v];} }signed main() {scanf( "%lld %s", &n, s + 2 );for( int i = 0;i <= n;i ++ ) {c[i][0] = c[i][i] = 1;for( int j = 1;j < i;j ++ )c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;}dfs( 1 );int ans = 0;for( int i = 1;i <= n;i ++ ) (ans += f[1][i]) %= mod;printf( "%lld\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的[CQOI2017] 老C的键盘（树形dp + 组合数）的全部內容，希望文章能夠幫你解決所遇到的問題。

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