SPOJ - PERIODNI

笛卡尔树，树形dp。

SP3734 PERIODNI

题意

给定一个 $N$ 列的表格，每列的高度各不相同，但底部对齐，然后向表格中填入 $K$ 个相同的数，填写时要求不能有两个数在同一列，或同一行，下图中 b 是错误的填写， a 是正确的填写，因为两个 a 虽然在同一行，但它们中间的表格断开。

$$1\le N,K \le 500,\,h_i\le 10^6$$

题解

先考虑一个 $n\times m$ 的矩形，选 $k$ 个格子，不能出现同行同列的方案数。

$$\binom{n}{k}\times \binom{m}{k} \times k!$$

考虑原题，因为连续的一行内只能放一个，所以可从下到上做如下切割（当前区间 $[l,r]$ 选择区间最小的 $h_x$，一刀切，得到左右两个独立的块 $[l,x-1]$ 和 $[x+1,r]$。重复即可）。这个操作实际上对区间建笛卡尔树，树上每个节点对应一个矩形。

然后树形 DP 即可，设 $f(u,i)$ 表示 $u$ 点子树中选 $i$ 个块的方案。
转移显然。

CODE

#include <bits/stdc++.h>
template <typename Tp>
inline void read(Tp &x) {
    x = 0; bool fg = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') fg ^= 1; ch = getchar();}
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
    if (fg) x = -x;
}
template <typename Tp, typename... Args>
void read(Tp &t, Args &...args) { read(t); read(args...); }
using namespace std;
typedef long long ll;
const int N = 505;
const int M = 1000010;
const int mod = 1e9 + 7;
ll inv[M], fac[M], ifac[M];
ll dp[N][N];
int h[N], n, K;
template<typename Tp> void Add(Tp &x, Tp y) { x = (x + y) % mod; }
struct node {
    int l, r;
} t[N]; int rt;
void build() {
    stack<int> stk;
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && h[stk.top()] > h[i])
            t[i].l = stk.top(), stk.pop();
        if (stk.empty()) rt = i;
        else t[stk.top()].r = i;
        stk.push(i);
    }
}
ll C(int n, int m) {
    if (n < m) return 0;
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
void dfs(int x, int l, int r, int H) {
    if (!x) return ;
    dfs(t[x].l, l, x - 1, h[x]); dfs(t[x].r, x + 1, r, h[x]);
    // length = r - l + 1, height = h[x] - H
    int len = r - l + 1, hei = h[x] - H;
    for (int i = 0; i <= x - l && i <= K; ++i) {
        for (int j = 0; j <= r - x && i + j <= K; ++j)
            Add(dp[x][i + j], dp[t[x].l][i] * dp[t[x].r][j] % mod);
    }
    for (int i = min(K, r - l + 1); i >= 1; --i) {
        for (int j = 1; j <= min(len, hei); ++j)
            Add(dp[x][i], dp[x][i - j] * C(hei, j) % mod * C(len - i + j, j) % mod * fac[j] % mod);
    }
}
int main() {
    read(n, K);
    for (int i = 1; i <= n; ++i) read(h[i]);
    if (K > n) { puts("0"); return 0; }
    build();
    inv[0] = inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for (int i = 2; i < M; ++i) fac[i] = fac[i - 1] * i % mod;
    for (int i = 2; i < M; ++i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 2; i < M; ++i) ifac[i] = ifac[i - 1] * inv[i] % mod;
    dp[0][0] = 1;
    dfs(rt, 1, n, 0);
    printf("%lld\n", dp[rt][K]);
    return 0;
}