bzoj2616

树形dp+笛卡尔树+单调栈

这道题跟树形dp有什么关系？

事实上，我们对矩形建立笛卡尔树，先找出最矮的矩形，向两边区间最矮的矩形连边，这样就构成了一棵二叉树，因为只有一个矮的区间会对高的区间造成影响，而且儿子之间不会互相影响，并且这样一层一层保证了每段矩形都会被覆盖到，其实就是单调栈，所以这样连是对的，然后跑一个树形背包，dp[i][j]表示i节点子树放了j个车，很明显两个儿子之间不会互相影响，所以自然是可以合并儿子之间的信息。

f[u][i]表示自己不放儿子放的方案数，dp[u][i]表示子树里放i个的方案数，然后转移一下就行了。一个 n*m的矩形内放k个的方案数是k!*C(n,k)*C(m,k)，选完行和列的交点后全排列表示所有交点。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = , mod = 1e9 + ;

int n, K, root;

int H[N], h[N], lc[N], rc[N], w[N];

ll dp[N][N], fac[], f[N][N];

void up(ll &x, const ll &t) { x = (x + t) % mod; }

ll power(ll x, ll t)

{

    ll ret = ;

    for(; t; t >>= , x = x * x % mod) if(t & ) ret = ret * x % mod;

    return ret;

}

ll inv(ll x) { return power(x, mod - ); }

ll C(int a, int b)

{

    if(a < b) return ;

    return fac[a] * inv(fac[b]) % mod * inv(fac[a - b]) % mod;

}

ll calc(int a, int b, int K)

{

    if(a < K || b < K) return ;

    ll ret = fac[K] * C(a, K) % mod * C(b, K) % mod;

    return ret;

}

void dfs(int u)

{

    f[u][] = dp[u][] = ;

    if(!u) return;

    dfs(lc[u]);

    dfs(rc[u]);

    for(int i = ; i <= K; ++i)

        for(int j = ; j <= i; ++j)

            up(f[u][i], dp[lc[u]][j] * dp[rc[u]][i - j] % mod);

    for(int i = K; i >= ; --i)

        for(int j = ; j <= i; ++j) if(f[u][j])

            up(dp[u][i], f[u][j] * calc(H[u], w[u] - j, i - j) % mod);

}

int build(int l, int r)

{

    if(l > r) return ;

    int p = l;

    for(int i = l; i <= r; ++i) if(h[i] < h[p]) p = i;

    lc[p] = build(l, p - );

    rc[p] = build(p + , r);

    H[lc[p]] = h[lc[p]] - h[p];

    H[rc[p]] = h[rc[p]] - h[p];

    w[p] = r - l + ;

    return p;

}

int main()

{

    scanf("%d%d", &n, &K);

    fac[] = ;

    for(int i = ; i <= n; ++i) scanf("%d", &h[i]), H[i] = h[i];

    for(int i = ; i <= ; ++i) fac[i] = fac[i - ] * (ll)i % mod;

    root = build(, n);

    dfs(root);

    printf("%lld\n", dp[root][K]);

    return ;

}

巴特西

bzoj2616

最新文章

热门文章