starship专题

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

题目:         链接:点击打开链接 题意:         n个房间组成一棵树,你有m个战队,从1号房间开始依次clear每个房间,在每个房间需要花费的战队个数是bugs/20,得到的价值是the possibility of capturing a brain,求最大的价值。 算法:        树形dp,有依赖的背包问题。(依次clear每个房间) 思路:

Hdu1011 Starship Troopers -- 树形背包

/*题意:星河战队要去完成任务:用有限的战士去俘获尽可能多的首脑。条件和注意:1:一颗树(没有重边,没有环,没有孤立点),表示敌军的基地地图2:一个战士可以战胜20个敌人,保证战士不重复战斗,不走回路。3:要想抓到首脑,必须要有战士进入房间。分析:树上跑背包。*/#include<iostream>#include<cstring>#include<algorithm>#inc

hdu 1011 starship troopers

这道题是一个树形 背包问题,或者说树形DP问题,房间的管道形成树。 背包问题的特点: 最优子结构,可分解, 解决办法: 常见的有递归(自顶向下),搜索(自底向上),背包注意的问题,为什么要自底向上搜索???? 需要好好学习背包问题; #include <iostream>#include<vector>#include<cstdio>#include<cstring>using n

windows下powershell与linux下bash美化教程(使用starship)

starship美化教程 Win11 + Powershell 安装 在命令行使用下面命令安装 # 安装starshipwinget install starship 将以下内容添加到 Microsoft.PowerShell_profile.ps1,可以在 PowerShell 通过 $PROFILE 变量来查询文件的位置 Invoke-Expression (&starship

HDU 1011 Starship Troopers

人一我百,人十我万!! 树形DP加上一些背包的思想,有一些模板的感觉。 ac code: #include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <cmath>#include <vector>#include <list>

zoj 2111 Starship Troopers(树形DP)

1、http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1111 2、题目大意: 题意是说有n个洞形成一棵树,你有m个士兵,每个洞都有一定数量的虫子和一定概率的首脑。每个士兵可以攻击20只虫子。而且想要攻击下面的洞的虫子,必须要攻击上层的虫子,问你花费这m个士兵,最多可以得到多少概率的首脑。 定义dp[x][y]表示在x结点

hdu-1011- Starship Troopers-自由树转二叉树+树形DP

题目很水,但是有很多易错点。。。 注意: 1,题目输入的时候是自由树,无向边。 2,如果某个点的bugs是0,也必须有至少一个士兵经过此点。 做法:: 按照题意,把自由树转为二叉树。 然后树形dp dp[x][y]:在二叉树中的x节点为根的树中,使用了y个士兵获得的最大值。 dp[x][y]=dp[node[x].l][k]+nval[x]+dp[node[x].r][y-k];