BZOJ 4013 - [HNOI2015]实验比较

#动态规划 #树形动态规划
Published on 2017-04-09

题目地址

描述

有 n(n≤100)n(n\le 100) 张图片，给定 m(m≤n)m(m\le n) 种 x = y 或是 x < y 的关系，其中只有 x = y 具有传递性，保证对于每个 ii，至多有一个条件满足 y=iy = i。求所有合法的图片之间的相对关系种类数。

分析

将每个图片看作一个点，假如我们将相等的图片缩成一个点，并且根据条件 x < y 连边 x→yx\to y，不难发现缩点后的图满足每个点的入度不大于一，所以缩点后的图，可以看做一个森林。

森林可能有多棵树，我们建立一个超级根连向所有的根，不难发现这样并不影响答案。现在问题可以转换为这样一个模型，给定一棵树，要求给所有的点赋一种标号，满足儿子的标号大于父亲的标号，求所有本质不同的标号方案总数。

这显然可以树形 DP，设 f(i,j)f(i, j) 为考虑以 ii 为根的子树，一共用了 jj 种标号的不同方案总数。对于转移，由于根节点肯定与子树标号不同，我们最后考虑。现在只需要考虑如何合并儿子 vv。设 g(i,j)g(i, j) 为考虑前 ii 个儿子，用了 jj 种标号的方案总数，那么

g(i,j)=∑k=0j(jk)g(i−1,k)∑l=j−kk(kl−(j−k))f(v,l) g(i, j) = \sum_{k = 0}^j\binom j kg(i - 1, k)\sum_{l =j -k}^k\binom k {l - (j - k)}f(v, l)

思路是，首先枚举之前用了几种，乘一下组合数，再枚举当前用了 ll 种，那么就有 l−(j−k)l - (j - k) 种标号与之前相同，需要再乘一下组合数。这样就能轻松转移了。

复杂度：O(n3)O(n^3)。

代码

//  Created by Sengxian on 2017/4/9.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 4013 树形 DP
#include <bits/stdc++.h>
#define len(x) ((int)x.size())
using namespace std;

typedef long long ll;
inline int readInt() {
    int n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100 + 3, MOD = 1000000007;
vector<int> G[MAX_N];
int n, m, cnt = 0;
int id[MAX_N];
bool vis[MAX_N];

void dfs(int u) {
    vis[u] = true, id[u] = cnt;
    for (int i = 0; i < len(G[u]); ++i) {
        int v = G[u][i];
        if (!vis[v]) dfs(v);
    }
}

void buildTree() {
    static int from[MAX_N], to[MAX_N], deg[MAX_N];
    int edgeCnt = 0;
    for (int i = 0; i < m; ++i) {
        int u, v;
        char op;
        scanf("%d %c %d", &u, &op, &v), --u, --v;
        if (op == '=') G[u].push_back(v), G[v].push_back(u);
        else from[edgeCnt] = u, to[edgeCnt] = v, ++edgeCnt;
    }

    for (int i = 0; i < n; ++i) {
        if (!vis[i]) ++cnt, dfs(i);
        G[i].clear();
    }

    for (int i = 0; i < edgeCnt; ++i) {
        deg[id[to[i]]]++;
        G[id[from[i]]].push_back(id[to[i]]);
    }

    ++cnt;
    for (int i = 1; i < cnt; ++i) if (deg[i] == 0) G[0].push_back(i);
    n = cnt;
}

int c[MAX_N][MAX_N], f[MAX_N][MAX_N], s[MAX_N];

void dp(int u) {
    if (vis[u]) puts("0"), exit(0);
    vis[u] = true;
    s[u] = 0, f[u][0] = 1;

    for (int i = 0; i < len(G[u]); ++i) {
        int v = G[u][i];
        dp(v);

        static int g[MAX_N];
        memset(g, 0, sizeof g);
        for (int j = 1; j <= s[u] + s[v]; ++j)
            for (int k = 0; k <= s[u]; ++k)
                for (int l = j - k; l <= j; ++l)
                    (g[j] += (ll)c[j][k] * f[u][k] % MOD * c[k][l - (j - k)] % MOD * f[v][l] % MOD) %= MOD;
        s[u] += s[v];    
        memcpy(f[u], g, sizeof g);
    }

    for (int i = s[u] + 1; i > 0; --i) f[u][i] = f[u][i - 1];
    f[u][0] = 0;
    ++s[u];
}

int main() {
    n = readInt(), m = readInt();

    buildTree();
    c[0][0] = 1;
    for (int i = 1; i < MAX_N; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
    }

    if (len(G[0]) == 0) puts("0"), exit(0);
    memset(vis, 0, sizeof vis);
    dp(0);

    int ans = 0;
    for (int i = 1; i <= n; ++i) (ans += f[0][i]) %= MOD;
    printf("%d\n", ans);

    return 0;
}
HNOI 2017 Day 1 题解