uvalive4015_uva4015-程序员宅基地

技术标签: 树形DP  01背包  

题目大意:
一棵n个节点的有根树,树的边有正整数权,表示两个节点之间的距离,你的任务是回答这样的询问,从根节点出发,走不超过x单位的距离,最多能走多少个节点,节点经过多次算一个,对于每次的询问输出:经过节点数最大的值

思路:
树形DP。
树形DP一般都是用三维结构完成的。
dp[i][j][k]表示根节点为i经过了j个节点,类似于01背包,k== 0表示返回,k == 1表示不返回。
所以如果返回的话只有一种情况就是根节点和子树都要返回
如果不返回的话就可能根返回子树不返回或者根不返回子树返回。

代码

#include <iostream>
using namespace std;
#include <cstring>
#include <stdio.h>
#include <vector>

const int maxn = 550;

int dp[maxn][maxn][2];
int n,son[maxn],cnt[maxn];
vector <int> g[maxn];

void dfs(int x) {
    for(int i = 1; i <= n; i++)
        dp[x][i][0] = dp[x][i][1] = 0x3f3f3f3f;
    dp[x][1][0] = dp[x][1][1] = 0;
    son[x] = 1;
    for(int i = 0; i < g[x].size();i += 2) {
        int y = g[x][i],w = g[x][i + 1];
        dfs(y);
        for(int j = son[x];j >0 ; j --) {
   //这里一定要倒着因为是01背包问题。
            for(int k = 1; k <= son[y]; k++) {
                dp[x][j + k][1] = min(dp[x][j + k][1],dp[x][j][1]+dp[y][k][1] + w * 2);
                dp[x][j + k][0] = min(dp[x][j + k][0],min(dp[x][j][0] + dp[y][k][1] + w * 2,dp[x][j][1] + dp[y][k][0] + w));
            }
        }
        son[x] += son[y];
    }
}

int main() {

    int T = 1;
    while(scanf("%d",&n) != EOF && n) {
        for(int i = 0; i <= n; i++)
            g[i].clear();
        memset(cnt,0,sizeof(cnt));
        for(int i = 1; i < n; i++) {
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            cnt[u]++;
            g[v].push_back(u);
            g[v].push_back(w);
        }
        int root = 0;
        for(int i = 1; i < n; i++)
            if(!cnt[i])
                root = i;
        dfs(root);
        int q,x;
        scanf("%d",&q);
        printf("Case %d:\n",T++);
        while(q--) {
            scanf("%d",&x);
            int ans = 1;
            for(int i = 1; i <= n; i++)
                if(dp[root][i][0] <= x)
                    ans = i;
            printf("%d\n",ans);
        }
    }
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/vv494049661/article/details/51249186

智能推荐

Android自定义状态栏颜色以与APP风格保持一致_dialogfragment 状态栏颜色-程序员宅基地

文章浏览阅读3.9k次。我们知道IOS上的应用,状态栏的颜色总能与应用标题栏颜色保持一致,用户体验很不错,那安卓是否可以呢?若是在安卓4.4之前,答案是否定的,但在4.4之后,谷歌允许开发者自定义状态栏背景颜色啦,这是个不错的体验!若你手机上安装有最新版的qq,并且你的安卓SDK版本是4.4及以上,你可以看下它的效果:实现此功能有两种方法:1.在xml中设置主题或自定义style; _dialogfragment 状态栏颜色

HTML中DIV与SPAN的区别_在html中span和div标签的区别-程序员宅基地

文章浏览阅读1.9w次,点赞10次,收藏23次。html的div和span, 经常会用到, 尤其是前者。 1. div是块级元素, 实际上就是一个区域, 主要用于容纳其他标签。 默认的display属性是block 2. span是行内元素, 主要用于容纳文字。 默认的display属性是inline 看看如下:test紧跟前面的"test"显示而这里会另起一行显示_在html中span和div标签的区别

神经网络设计_学习规则总结_神经元的学习规则-程序员宅基地

文章浏览阅读3.1k次。学习规则,就修改神经网络的权值和偏置值的过程和方法,其目的是为了训练网络来完成某些工作。 学习规则主要有3种类型:有监督学习、无监督学习和增强学习。1,有监督学习 根据输入和目标输出(注意区分目标输出和实际输出!)来调整权值和偏置值。2,无监督学习 仅仅根据网络的输入调整网络的权值和偏值,没有目标输出。3,感知机学习规则_有监督学习_神经元的学习规则

Office 2016自定义安装需要的组件_office2016 deployoffice-程序员宅基地

文章浏览阅读4.5k次。Office 2016部署工具下载 https://www.microsoft.com/en-us/download/details.aspx?id=49117配置文件在线编辑 http://officedev.github.io/Office-IT-Pro-Deployment-Scripts/XmlEditor.htmlOffice 部署工具概述 https://docs.mic..._office2016 deployoffice

RH124(6)----Linux系统中的权限管理_stripped, too many notes-程序员宅基地

文章浏览阅读203次。文章目录一、权限查看及读取1、权限查看2、权限的读取二、普通权限的类型及作用1、用户对文件的身份2、权限位3、用户身份匹配4、权限类型三、设定普通权限的方法四、系统默认权限设定五、文件用户用户组管理六、特殊权限stickyid 粘制位sgid 强制位suid 冒险位七、acl权限列表acl列表开启标识acl列表权限读取acl列表的控制acl 权限优先级acl mask 控制acl 列表的默认权限八、attr权限一、权限查看及读取1、权限查看ls -l file ##查看文件权限ls -ld dir _stripped, too many notes

2018 年了,你还是只会 npm install 吗?-程序员宅基地

文章浏览阅读123次。本文同步发表于作者博客: 2018 年了,你还是只会 npm install 吗?nodejs 社区乃至 Web 前端工程化领域发展到今天,作为 node 自带的包管理工具的 npm 已经成为每个前端开发者必备的工具。但是现实状况是,我们很多人对这个nodejs基础设施的使用和了解还停留在: 会用 npm install 这里(一言不合就删除整个 node_modules 目录然后重新 in..._npm i webpack -g和npm install一样吗

随便推点

技术小白成长之路 - 谷歌云端 GCP Cloud Engineering - 第一篇 - 核心架构 Core Infrastructure-程序员宅基地

文章浏览阅读3k次,点赞4次,收藏24次。谷歌云端 GCP Cloud Engineering - 第一篇 - 平台交互谷歌云端平台GCP简介二级目录三级目录1. 谷歌云端平台GCP资源层次结构2. VPC Network3. 存储与数据库Cloud Storage和Cloud BigtableCloud SQL和Cloud Spanner容器,K8S, 与K8S Engine4. --- App Engine云开发谷歌云端平台GCP简..._gcp cloud

JLINK SW接线方式_jlink接线方式-程序员宅基地

文章浏览阅读5.4k次,点赞2次,收藏6次。从右上到左下1:3.3v7:swio9:swclk20:GND_jlink接线方式

LeetCode(力扣)题目中二叉树的如何生成?根据给定顺序列表生成二叉树(python)-程序员宅基地

文章浏览阅读3.4k次,点赞24次,收藏21次。在刷 leetcode 二叉树相关的题目时,经常有这样给定的例子,例如: 检查平衡性实现一个函数,检查二叉树是否平衡。在这个问题中,平衡树的定义如下:任意一个节点,其两棵子树的高度差不超过 1。示例 1:给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7返回 true 。示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \_列表生成二叉树

oryx 推荐系统_Cloudera为Hadoop带来机器学习开源工具Oryx-程序员宅基地

文章浏览阅读70次。Hadoop发行商Cloudera去年收购伦敦的创业公司Myrrix时,并未引起业界太多关注,其后Cloudera也很少宣传公司在机器学习方面的技术。但是Myrrix的的技术和其创始人Sean Owen在机器学习方面的价值和影响力不容小觑。Owen目前正在开发一个开源机器学习项目——Oryx(大羚羊,Cloudera还销售一款产品叫黑斑羚,Impala)。Oryx的目标是帮助Hadoop用户搭建并..._oryx cloudera

Android DDMS Dump View Hierarchy 调试界面环境搭建_android dump view信息-程序员宅基地

文章浏览阅读2.3k次。Android DDMS Dump View Hierarchy 调试界面环境搭建sdk/tools/monitor.bat 双击打开,点击 Dump View Hierarchy 抓取ui界面jdk环境版本要为jdk1.8左右的,比较新的jdk环境,会导致sdk/tools/monitor.bat 双击打不开。比如:我用的是:openjdk-8u41-b04-windows-i586-14_jan_2020.zip是从https://jdk.java.net/java-se-ri/8-MR3网址_android dump view信息

iOS--3分钟教会你用mathjax显示数学公式_mathjar 显示数学公式-程序员宅基地

文章浏览阅读9.5k次,点赞9次,收藏3次。iOS–3分钟教会你用mathjax显示数学公式_mathjar 显示数学公式

推荐文章

热门文章

相关标签