hdu 1011 Starship Troopers (依赖背包 树形dp)

2024-08-30 03:08

本文主要是介绍hdu 1011 Starship Troopers (依赖背包 树形dp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

        链接:点击打开链接

题意:

        n个房间组成一棵树,你有m个战队,从1号房间开始依次clear每个房间,在每个房间需要花费的战队个数是bugs/20,得到的价值是the possibility of capturing a brain,求最大的价值。

算法:

       树形dp,有依赖的背包问题。(依次clear每个房间)

思路:

        状态转移dp[i][j]表示根结点为i时(房间i)花费j个战队能够得到的最大价值(捕捉到一个brain最大的可能值)。递归求出每个根结点处的最大值,最后dp[1][m]就是答案。

代码:

/*树型dp*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110struct Node
{int num;int p;
} node[MAXN];int n,m;
int dp[MAXN][MAXN];//dp[i][j]表示根结点为i(房间i)时,用j个战队能够捕捉一个brain最大的可能值
int vis[MAXN];
int tree[MAXN][MAXN];//存树void dfs(int root)
{int numm = (node[root].num+19)/20;vis[root] = 1;for(int i=numm; i<=m; i++)//初始化dp[root][i] = node[root].p;for(int i=1; i<=tree[root][0]; i++){int u = tree[root][i];if(vis[u])dfs(u);for(int j=m; j>=numm; j--)//01背包处理(转化为物品组,按分组背包){for(int k=1; k+j<=m; k++){if(dp[u][k])dp[root][j+k] = max(dp[root][j+k],dp[root][j]+dp[u][k]);}}}
}int main()
{//freopen("input.txt","r",stdin);int a,b;while(scanf("%d%d",&n,&m) != EOF && (n!=-1 || m!=-1)){memset(dp,0,sizeof(dp));memset(vis,0,sizeof(vis));memset(tree,0,sizeof(tree));for(int i=1; i<=n; i++)scanf("%d%d",&node[i].num,&node[i].p);for(int i=1; i<=n-1; i++){scanf("%d%d",&a,&b);tree[a][0]++;tree[a][tree[a][0]] = b;tree[b][0]++;tree[b][tree[b][0]] = a;}if(m == 0)printf("0\n");else{dfs(1);printf("%d\n",dp[1][m]);}}return 0;
}

---------------------------------------------------------------------------------

        我还没有理解依赖背包问题的解法和思路,看了别人的还是不能够领悟,真是菜菜菜啊~~~~~~代码来自点击打开链接

-----------------------------------------------------------------------------------------------------

战斗,永不停歇。。。。。。。。我对今天的态度就是对我一生的态度。。。。。

这篇关于hdu 1011 Starship Troopers (依赖背包 树形dp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1119627

相关文章

Maven如何手动安装依赖到本地仓库

《Maven如何手动安装依赖到本地仓库》:本文主要介绍Maven如何手动安装依赖到本地仓库问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、下载依赖二、安装 JAR 文件到本地仓库三、验证安装四、在项目中使用该依赖1、注意事项2、额外提示总结一、下载依赖登

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》:本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem

Python如何快速下载依赖

《Python如何快速下载依赖》本文介绍了四种在Python中快速下载依赖的方法,包括使用国内镜像源、开启pip并发下载功能、使用pipreqs批量下载项目依赖以及使用conda管理依赖,通过这些方法... 目录python快速下载依赖1. 使用国内镜像源临时使用镜像源永久配置镜像源2. 使用 pip 的并

python安装whl包并解决依赖关系的实现

《python安装whl包并解决依赖关系的实现》本文主要介绍了python安装whl包并解决依赖关系的实现,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录一、什么是whl文件?二、我们为什么需要使用whl文件来安装python库?三、我们应该去哪儿下

Spring AI Alibaba接入大模型时的依赖问题小结

《SpringAIAlibaba接入大模型时的依赖问题小结》文章介绍了如何在pom.xml文件中配置SpringAIAlibaba依赖,并提供了一个示例pom.xml文件,同时,建议将Maven仓... 目录(一)pom.XML文件:(二)application.yml配置文件(一)pom.xml文件:首

使用maven依赖详解

《使用maven依赖详解》本文主要介绍了Maven的基础知识,包括Maven的简介、仓库类型、常用命令、场景举例、指令总结、依赖范围、settings.xml说明等,同时,还详细讲解了Maven依赖的... 目录1. maven基础1.1 简介1.2 仓库类型1.3 常用命令1.4 场景举例1.5 指令总结