【树上背包】选课

我就是我 2024-03-17 11:27 8阅读 0赞

[P2014 \[CTSC1997\] 选课 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P2014 _CTSC1997_ _ - _ _ _ _luogu.com.cn]

题意：

![9eca9e28d91f4c09b7d8dd76a5da6fea.png][]

这下终于懂树上背包了

才知道原来树上背包的状态表示里一直是滚动了一维，怪不得之前怎么看都觉得很奇怪

滚动的是【前i个子树】

OIwiki里是这样写的：

![b601e8d08b0b46b081da892c6caa5c0b.png][]

这下看起来和普通背包没区别了

注意，因为滚动了一维，所以j需要倒着枚举

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=3e2+10,mxe=3e2+10;
    struct ty{
        int to,next;
    }edge[mxe<<1];
    int n,m,x,tot=0,rt;
    int a[mxn],head[mxn],in[mxn],dp[mxn][mxn],sz[mxn];
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
        }
    }
    void dfs(int u,int fa){
        sz[u]=a[u];dp[u][1]=a[u];
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u);
            sz[u]+=sz[edge[i].to];
            for(int j=m;j>=1;j--){
                for(int k=j-1;k>=0;k--){
                    dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[edge[i].to][k]);
                }
            }
        }
    }
    void solve(){
        cin>>n>>m;
        m++;
        init();
        for(int i=1;i<=n;i++){
            cin>>x>>a[i];
            add(x,i);
            add(i,x);
            in[i]++;
        }
        for(int i=0;i<=n;i++){
            if(!in[i]){
                rt=i;
                break;
            }
        }
        dfs(rt,-1);
        cout<<dp[0][m]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

全新版本：

#include <bits/stdc++.h>
    
    using i64 = long long;
    
    using namespace std;
    
    const int N = 2e3 + 10;
    
    vector<int> adj[N];
    
    int n, m;
    int Fa;
    int a[N], sz[N];
    int dp[N][N];
    
    void dfs(int u, int fa) {
        sz[u] = 0;
        for (auto v: adj[u]) {
            if (v == fa) continue;
            dfs(v, u);
            static int t[N];
            memset(t, -0x3f, sizeof(t));
            for (int j = 0; j <= sz[u]; j ++ ) {
                for (int k = 0; k <= sz[v]; k ++ ) {
                    t[j + k] = max(t[j + k], dp[u][j] + dp[v][k]);
                }
            }
            for (int j = 0; j <= sz[u] + sz[v]; j ++ ) {
                dp[u][j] = t[j];
            }
            sz[u] += sz[v];
        }
        sz[u] ++;
        for (int j = n; j >= 0; j --) {
            dp[u][j] = dp[u][j - 1] + a[u];
        }
        dp[u][0] = 0;
    }
    void solve() {
        cin >> n >> m;
        m ++;
    
        for (int i = 1; i <= n; i ++) {
            int u, v;
            cin >> Fa >> v;
            adj[i].push_back(Fa);
            adj[Fa].push_back(i);
            a[i] = v;
        }
        dfs(0, -1);
        cout << dp[0][m] << "\n";
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int t = 1;
        while (t-- ) {
            solve();
        }
        return 0;
    }

[P2014 _CTSC1997_ _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P2014
[9eca9e28d91f4c09b7d8dd76a5da6fea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/8aeeaead97764c87a13971db75d42f0b.png
[b601e8d08b0b46b081da892c6caa5c0b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/89d92a88bdef4cf086d13a0b5c8f8080.png