• Luogu P2014 [CTSC1997]选课
• Luogu U53204 【数据加强版】选课
• ouuan的博客 树上背包的上下界优化

暴力枚举 O(n3)

const int M = int(3e2) + 9;
const int N = int(3e2) + 9;
int dp[N][M], cost[N], value[N]; VI adj[N];
int n, m;

void dfs(int u = 0) {
    FLC(dp[u], 0x80);
    DWN_1(i, m, cost[u]) dp[u][i] = value[u];

    for (auto v: adj[u]) {
        dfs(v);
        DWN_1(i, m, cost[u]) {
            FOR_1(j, cost[u], i) {
                checkMax(dp[u][i], dp[u][j] + dp[v][i-j]);
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
    RD(n, m);
    REP_1(i, n) {
        int p; RD(p, value[i]); cost[i] = 1;
        adj[p].push_back(i);
    }
    dfs();
    cout << dp[0][m] << endl;
}

状态继承 O(n2)

const int N = int(1e5) + 9;
const int M = int(1e5) + 9;
int cost[N], value[N]; VI adj[N];
int n, m;

void dfs(int u, int m, VI& dpu) {
    m -= cost[u];
    for (auto v: adj[u]) {
        VI dpv = dpu; dfs(v, m, dpv);
        FOR_1(i, 0, m) checkMax(dpu[i], dpv[i]);
    }
    m += cost[u];
    DWN_1(i, m, cost[u]) dpu[i] = dpu[i-cost[u]] + value[u];
    REP(i, cost[u]) dpu[i] = -INF;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
    RD(n, m);
    REP_1(i, n) {
        int p; RD(p, value[i]); cost[i] = 1;
        adj[p].push_back(i);
    }
    VI dp0; dp0.resize(m+1);
    dfs(0, m, dp0);
    cout << dp0[m] << endl;
}

P1273 有线电视网
https://www.luogu.com.cn/problem/P1273

const int N = (3e3) + 9;
VII adj[N]; int sz[N];
int dp[N][N], bonus[N];
int n, m, z;

bool isLeaf(int u) {
    return u > n-m;
}

void dfs0(int u) {
    sz[u] = isLeaf(u);
    for (auto e: adj[u]) {
        int v = e.fi;
        dfs0(v);
        sz[u] += sz[v];
    }
}

void dfs(int u) {
    FLC(dp[u], 0x80);
    dp[u][0] = 0;

    if (isLeaf(u)) {
        dp[u][1] = bonus[u];
        return;
    }

    for (auto e: adj[u]) {
        int v = e.fi, w = e.se;
        dfs(v);
        DWN_1(i, sz[u], 1) {
            REP_1(j, sz[v]) {
                checkMax(dp[u][i], dp[u][i-j] + dp[v][j] - w);
            }
        }
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
    RD(n, m); REP_1(u, n-m) {
        Rush {
            int v, c; RD(v, c);
            adj[u].PB({v,c});
        }
    }

    FOR_1(u, n-m+1, n) RD(bonus[u]);

    dfs0(1); dfs(1);
    DWN_1(i, m, 0) {
        if (dp[1][i] >= 0) {
            cout << i << endl;
            return 0;
        }
    }
}

道路重建

https://www.luogu.com.cn/problem/P1272
https://www.luogu.com.cn/problem/U53878

const int N = (1e5) + 9;
VI adj[N]; int sz[N];
int n, m, z;

VI dp[N];
// dp[u][i]，保留 u 节点同时子树再保留 i 个节点的子树，最少删多少边

void dfs(int u, int p){

    sz[u] = 1; dp[u].PB(0);

    for (auto v: adj[u]) if (v != p) {
        dfs(v, u);

        REP(i, SZ(dp[u])) dp[u][i] += 1;
        DO(min(sz[v], m+1-sz[u])) dp[u].PB(INF);
        sz[u] += sz[v];

        DWN(i, SZ(dp[u]), 1) {
            REP(j, min(SZ(dp[v]), i)) {
                checkMin(dp[u][i], dp[u][i-1-j] + dp[v][j] - 1);
            }
        }
    }

    if (sz[u] > m) checkMin(z, dp[u][m] + bool(p));
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
    RD(n, m); --m; DO(n-1){
        int a, b; RD(a, b);
        adj[a].PB(b);
        adj[b].PB(a);
    }
    z = INF; dfs(1, 0);
    cout << z << endl;
}

Posted by xiaodao
Category: 日常