树形背包90tle

KANO07 @ 2024-02-22 21:20:07

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
vector<int>edge[65];
int cost[65], val[65];
int dp[65][40005];
int m,n;

void dfs(int u){
    for(int v : edge[u]){
        dfs(v);
        for(int j = n; j >= 0; j--){ //父树内存 
            for(int k = j; k >= cost[v]; k--){ //子树内存 
                dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k - cost[v]] + val[v]); 
            }
        }
    } 
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    n /= 10;
    for(int i = 0; i <= m; i++) edge[i].clear(); 
    for(int i = 1; i <= m; i++){
        int c,v,k;
        cin>>c>>v>>k;
        cost[i] = c/10;
        val[i] = v*c;
        edge[k].emplace_back(i);
    }
    dfs(0);
    cout<<dp[0][n]<<endl;
    return 0;
}

by QuQ_ @ 2024-02-22 21:23:52

@KANO07

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
vector<int>edge[65];
int cost[65], val[65];
int dp[65][40005];
int m,n;

void dfs(int u){
    for(int v : edge[u]){
        dfs(v);
        for(int j = n; j >= 0; j--){ //父树内存 
            for(int k = j; k >= cost[v]; k--){ //子树内存 
                dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k - cost[v]] + val[v]); 
            }
        }
    } 
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    n /= 10;
    edge[0].clear();
    for(int i = 1; i <= m; i++){
        edge[i].clear(); 
        int c,v,k;
        cin>>c>>v>>k;
        cost[i] = c/10;
        val[i] = v*c;
        edge[k].emplace_back(i);
    }
    dfs(0);
    cout<<dp[0][n]<<"\n";
    return 0;
}

by QuQ_ @ 2024-02-22 21:24:09

@KANO07 TLE解决了，但是WA

by QuQ_ @ 2024-02-22 21:24:52

@KANO07 #11WA了，建议打表

by QuQ_ @ 2024-02-22 21:26:39

@KANO07 好吧不开O2还是TLE

by Fu_Tao @ 2024-03-13 21:15:26

这是我受启发写的树形dp能AC

#include <iostream>
#include <vector>
using namespace std;
typedef int ll;
ll n,m,f[61][100001];
ll v,p,q;
vector<ll> vec[101];
struct node{
    ll pri,val;
}a[101];
void dfs(ll s){
    for(int i=0;i<vec[s].size();i++){
        ll k=vec[s][i];
        dfs(k);
        for(int j=n;j>=0;j--){
            for(int l=j;l>=a[k].pri;l--){
                f[s][j]=max(f[s][j],f[s][j-l]+f[k][l-a[k].pri]+a[k].val);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    n/=10;
    for(int i=1;i<=m;i++){
        cin>>v>>p>>q;
        a[i].pri=v/10;
        a[i].val=v*p;
        vec[q].push_back(i);
    }
    dfs(0);
    cout<<f[0][n];
    return 0;
}

by jiushibayu @ 2024-11-25 21:28:15

@Fu_Tao大佬能解释一下状态转移方程吗TAT