[JSOI2008] 魔兽地图

· · 题解

思路

设 f_{i, j, k} 表示在 i 号点的子树中，用 k 枚金币，使得 i 号装备多出 j 个的最大力量值之和。

容易得出一个 O(\lim ^2nm^2) 的 dag 上 dp，lim 为每件装备制成的数量的限制。

这时我们需要一个临时数组 g_{i,j} 表示当前点上，用 j 枚金币，造出 i 个当前装备的最大力量值之和，它与 f 的区别在于不用管当前点所表示装备的力量值，转移式如下。

for (int i = lim[u]; i >= 0; i -- )
    for (int j = h[u]; ~j; j = ne[j]) {
        int ver = e[j];
        for (int xx = m; xx >= 0; xx -- ) {
            int tmp = -INF;
            for (int yy = 0; yy <= xx; yy ++ )
                chkmax(tmp, g[i][xx - yy] + f[ver][i * w[j]][yy]);
            g[i][xx] = tmp;
        }
    }

这样就可以省掉一个 O(\lim)，接下来就可以用 g 推出 f。

for (int i = lim[u]; i >= 0; i -- )
    for (int j = 0; j <= i; j ++ )
        for (int k = 0; k <= m; k ++ )
            chkmax(f[u][j][k], g[i][k] + (i - j) * value[u]);

总时间复杂度 O(\lim n m^2)。

代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define re register
#define sz(x) (int(x.size()))
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 110, M = 2010, INF = 0x3f3f3f3f;
int n, m;
int d[N], lim[N], price[N], g[N][M], value[N];
int h[N], e[N * N], w[N * N], ne[N * N], idx;
int f[N][N][M], ans[M];
bool vis[N];

int rd() {
    int w = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {w = (w << 3) + (w << 1) + ch - 48; ch = getchar();}
    return f * w;
}

void chkmax(int &x, int y) {x = max(x, y);}

void add_edge(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    d[b] ++ ;
}

void dfs(int u) {
    if(vis[u]) return;
    vis[u] = true;
    if (h[u] == -1) {
        lim[u] = min(lim[u], m / price[u]);
        for (int i = lim[u]; i >= 0; i -- )
            for (int j = i; j <= lim[u]; j ++ )
                f[u][i][j * price[u]] = value[u] * (j - i);
        return;
    }
    lim[u] = 1e9;
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        dfs(ver);
        lim[u] = min(lim[u], lim[ver] / w[i]);
        price[u] += price[ver] * w[i];
    }
    lim[u] = min(lim[u], m / price[u]);
    memset(g, -0x3f, sizeof(g));
    for (int i = 0; i <= lim[u]; i ++ ) g[i][0] = 0;
    for (int i = lim[u]; i >= 0; i -- )
        for (int j = h[u]; ~j; j = ne[j]) {
            int ver = e[j];
            for (int xx = m; xx >= 0; xx -- ) {
                int tmp = -INF;
                for (int yy = 0; yy <= xx; yy ++ )
                    chkmax(tmp, g[i][xx - yy] + f[ver][i * w[j]][yy]);
                g[i][xx] = tmp;
            }
        }
    for (int i = lim[u]; i >= 0; i -- )
        for (int j = 0; j <= i; j ++ )
            for (int k = 0; k <= m; k ++ )
                chkmax(f[u][j][k], g[i][k] + (i - j) * value[u]);
}

int main() {
    memset(f, -0x3f, sizeof(f));
    memset(h, -1, sizeof(h));
    n = rd(), m = rd();
    for (int i = 1; i <= n; i ++ ) {
        value[i] = rd();
        char c;
        cin >> c;
        if (c == 'A') {
            int tm = rd(), x, y;
            while (tm -- ) x = rd(), y = rd(), add_edge(i, x, y);
        } else price[i] = rd(), lim[i] = rd();
    }
    for (int i = 1; i <= n; i ++ )
        if(!d[i]) {
            dfs(i);
            for (int j = m; j >= 0; j -- )
                for (int k = 0; k <= j; k ++ )
                    chkmax(ans[j], ans[j - k] + f[i][0][k]);
        }
    printf("%d\n", ans[m]);
    return 0;
}