首页 技术 正文
技术 2022年11月18日
0 收藏 447 点赞 3,249 浏览 550 个字

题目链接:  poj-3345  hdu-2415

题意

有n个国家,你要获取m个国家的支持,获取第i个国家的支持就要给cost[i]的价钱
   其中有一些国家是老大和小弟的关系,也就是说,如果你获得了某个老大国家的支持,
   那么这个国家的所有小弟(包括小弟的小弟…递归下去)都会无偿免费支持你。
   问最少的花费可以得到m个国家的支持

思路

这题还是比较好想的树形dp, 不过输入有些麻烦, 一开始以为每组样例结束都是’#’,结果一直
   RE,后来发现最后一组才是 ‘#’…
   国家由于是直接给名字的,所以我用map<string, int>来映射保存编号。

老大和小弟的关系, 其实就是组成了一棵棵的树,那么所有国家的关系就是一个森林。
   为了方便进行树形dp, 在增加一个“超级根节点”,森林里所有树的根节点是“超级根节点”的儿子。

那么,用f(i, j)表示子树i, 获取j个国家支持的最少花费

对于子树i,所有节点i的儿子节点都是一组物品,
   对于某个儿子,可以选择让他支持1,2..,j个, 那么就是对所有儿子进行分组背包了。。

用tot[v]表示子树v的节点个数
   状态转移为:
   f[u][i] = min{ f[u][i], f[u][i-j] + f[v][j] | 1<=j<=tot[v] && j<=i && v是u的儿子 };

代码

 

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:8,997
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,511
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,356
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,139
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,770
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,848