依赖背包变形——hdu4003

青旅半醒 2023-10-12 08:19 26阅读 0赞

思维性比较强，代码挺简单的，dp\[u\]\[j\]表示在u子树下安排j个机器人，让其不回u

注意转移时的初始值

/*
    dp[u][j]为在子树u有j个机器人不回来 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define N 10005
    struct Edge{
        int to,nxt,w;}e[N<<1];
    int head[N],tot,n,k,s;
    void init(){
        memset(head,-1,sizeof head);tot=0;
    }
    void add(int u,int v,int w){
        e[tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot++;
    }
    int dp[N][20];
    void dfs(int u,int pre){
        for(int i=head[u];i!=-1;i=e[i].nxt){
            int v=e[i].to;
            if(v==pre)continue;
            dfs(v,u);
            for(int j=k;j>=0;j--){
                dp[u][j]=2*e[i].w+dp[v][0]+dp[u][j];
                for(int l=1;l<=j;l++)
                    dp[u][j]=min(dp[u][j],dp[u][j-l]+dp[v][l]+l*e[i].w);//给v子树l个机器人 
            }
        }
    }
    
    int main(){
        while(cin>>n>>s>>k){
            init();
            for(int i=1;i<n;i++){
                int u,v,w;scanf("%d%d%d",&u,&v,&w);
                add(u,v,w);add(v,u,w);
            }
            memset(dp,0,sizeof dp);
            dfs(s,s);
            int ans=0x3f3f3f3f;
            for(int i=0;i<=k;i++)
                ans=min(ans,dp[s][i]);
            cout<<ans<<'\n';
        }
        return 0;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11387665.html

发表评论取消回复

表情：

评论列表（有 0 条评论，26人围观）

还没有评论，来说两句吧...

相关阅读

相关依赖背包变形——hdu4003

思维性比较强，代码挺简单的，dp\[u\]\[j\]表示在u子树下安排j个机器人，让其不回u 注意转移时的初始值 / dp[u][j]为在子树u有j个机器人

青旅半醒/ 2023年10月12日 08:19/ 0 赞/ 27 阅读

相关依赖背包变形（经典）——poj1155

这个题用优化后的依赖背包做难以实现，所以用常规的泛化物品的和来做即可每个节点的容量定义为这个节点下的叶子结点个数，dp\[u\]\[j\]用来表示节点u下选取j个物品的最大

偏执的太偏执、/ 2023年10月12日 08:18/ 0 赞/ 33 阅读

相关依赖背包优化——hdu1561

傻逼依赖背包的优化 include<bits/stdc++.h> using namespace std; define N 205 str

爱被打了一巴掌/ 2023年10月12日 08:18/ 0 赞/ 26 阅读

相关依赖背包变形——poj1947（经典）

/ 这题显然不适用依赖背包的优化，因为不能保证根是必选的，但是可以按照常规依赖背包的思路进行转移，即每次对一个儿子进行C^2的转移还是树形的背包，d

蔚落/ 2023年10月12日 08:18/ 0 赞/ 48 阅读

相关 hdu 4003 Find Metal Mineral 【树形dp，分组背包】

题目：[hdu 4003 Find Metal Mineral ][hdu 4003 Find Metal Mineral] 题意：火星上发现了一些n个矿厂，有 k

淡淡的烟草味﹌/ 2022年09月21日 00:29/ 0 赞/ 243 阅读

相关 hdu 1561 （树形dp+依赖背包）

ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻

矫情吗；*/ 2022年08月21日 03:23/ 0 赞/ 284 阅读

相关 HDU 2955-Robberies（01背包变形）

Robberies Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot

青旅半醒/ 2022年07月24日 05:24/ 0 赞/ 227 阅读

相关 HDU-3449-Consumer（有依赖背包）

Consumer Problem Description FJ is going to do some shopping, and befor

骑猪看日落/ 2022年05月26日 13:45/ 0 赞/ 204 阅读

相关 HDU2955 Robberies————01背包变形

Robberies Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Oth

系统管理员/ 2022年05月17日 07:35/ 0 赞/ 263 阅读

相关 HDU1114 Piggy-Bank————01背包变形

Piggy-Bank Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

迈不过友情╰/ 2022年05月17日 07:21/ 0 赞/ 257 阅读