HDU1561 The more, The Better(树形DP)
2024-10-15 23:48:33
题目是有n个存有宝藏的城堡,攻克任何一个城堡都需要先攻克0个或其他1个城堡,问攻克m个城堡最多能得到多少宝藏。
题目给的城堡形成一个森林,添加一个超级根把森林连在一起就是树了,那么就考虑用树型DP:
- dp[u][m]表示以u结点为根的子树攻克m个结点的最大价值
但是这样转移太难了,根是从每个孩子通过各自分配若干的城堡去攻克转移的,一个排列组合数,阶乘,是指数级的时间复杂度!
看了题解,原来这是依赖背包,没看背包九讲。。不过网上的博客似乎没说清楚,事实上这个状态应该是三个维度来表示:
- dp[u][m][n]表示以u结点为根的子树,且只考虑u结点的前n个孩子,去攻克m个结点,所能得到的最大价值
- 转移就是dp[u][m][n]=max(dp[u][m-k][n-1]+dp[u的第n个孩子][k][u的孩子个数])(0<=k<m)
可以发现n只从n-1转移而来,那么就可以像01背包重复利用内存,这三维数组只用二维数组来实现,即:
- dp[u][m]=max(dp[u][m-k]+dp[u’][k])(father[u']=u,0<=k<m)
- m要从大到小枚举。
代码感觉还不好实现。。感觉这题挺难的= =虽然听说这是树型DP入门题。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge{
int u,v,next;
}edge[];
int NE,head[];
void addEdge(int u,int v){
edge[NE].u=u; edge[NE].v=v; edge[NE].next=head[u];
head[u]=NE++;
}
int val[],d[][];
void dp(int u,int m){
d[u][]=val[u];
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
dp(v,m);
for(int j=m; j>=; --j){
for(int k=; k<j; ++k){
d[u][j]=max(d[u][j],d[u][j-k]+d[v][k]);
}
}
}
}
int main(){
int n,m,a;
while(~scanf("%d%d",&n,&m) && (n||m)){
NE=;
memset(head,-,sizeof(head));
for(int i=; i<=n; ++i){
scanf("%d%d",&a,val+i);
addEdge(a,i);
}
memset(d,,sizeof(d));
dp(,m+);
printf("%d\n",d[][m+]);
}
return ;
}
最新文章
- clear属性
- mysql忘记密码的重置方法
- Sphinx+MySQL5.1x+SphinxSE+mmseg
- ed编辑器使用
- EasyBCD 硬盘安装Pear OS
- SharePoint Services 数据库表
- 环状DNA序列
- they're hiring
- 剑指offier第4题
- CentOS 7.3 minimal 开启网络服务
- activeMq的入门程序
- el-input的color修改无效问题
- python添加post请求
- Sublime Text 3安装emmet(ZenCoding)
- windos64位下python3.6安装pywin32的问题
- Jira配置openLdap服务器进行用户认证
- 【英文文档】Solidifier for Windows Installation Guide
- 关于CPU的User、Nice、System、Wait、Idle各个参数的解释
- vue实现带规格商品的表格编辑
- Angular4.+ ngx-bootstrap Pagination 自定义分页组件