2020ICPC 南京 Monster Hunter(树形依赖背包)

2024-04-15 23:18

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

好久没写树形DP手生疏了。

题意:
每个点权值为 h p [ x ] + h p [ v ] hp[x]+hp[v] hp[x]+hp[v],其中 v v v x x x的儿子。你可以删掉 m m m个点,求对于 0 ≤ m ≤ n 0≤m≤n 0mn的每个 m m m能得到的最小权值和。

思路:
定义 d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1]代表点 i i i为根子树,删掉了 j j j个点, i i i是否被删能得到的最小权值和。
转移就是按照基本的背包转移,不再赘述。

但是注意一点,转移过程中其实隐含了 d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1]是前 x x x个子树得到的结果,所以这里其实有滚动的过程,要开个临时数组。以前写这种类型题的时候由于是求最大权值和,所以可以直接转移过去,不需要滚动或者开临时数组。但是这里是取最小值,很必要,结果赛中写的时候输出的结果一直是INF ┭┮﹏┭┮。

ps:还有这个转移居然是 n 2 n^2 n2的,我还想着按照子树大小排个序看看能否水一水或者dfs序优化(想写,但是不知道怎么初始化状态),结果这居然是正解XD。不过冷静分析一下还是可以发现,转移实际就是枚举任意两点LCA,所以复杂度 n 2 n^2 n2

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;
const int maxn = 2e3 + 7;
typedef long long ll;
const ll INF = 1e18;
vector<int>G[maxn];
ll dp[maxn][maxn][2],tmp[maxn][2];
ll hp[maxn];
int siz[maxn];void dfs(int x) {siz[x] = 1;for(int t = 0;t < G[x].size();t++) {int v = G[x][t];dfs(v);for(int i = 0;i <= siz[x] + siz[v];i++) {tmp[i][0] = tmp[i][1] = INF;}for(int i = 0;i <= siz[x];i++) {for(int j = 0;j <= siz[v];j++) {tmp[i + j][0] = min(tmp[i + j][0],dp[x][i][0] + dp[v][j][0] + hp[v]);if(j > 0) {tmp[i + j][0] = min(tmp[i + j][0],dp[x][i][0] + dp[v][j][1]);}if(i > 0) {tmp[i + j][1] = min(tmp[i + j][1],dp[x][i][1] + dp[v][j][0]);}if(i > 0 && j > 0) {tmp[i + j][1] = min(tmp[i + j][1],dp[x][i][1] + dp[v][j][1]);}}}for(int j = 0;j <= siz[x] + siz[v];j++) {dp[x][j][0] = tmp[j][0];dp[x][j][1] = tmp[j][1];}siz[x] += siz[v];}for(int i = 0;i <= siz[x];i++) {dp[x][i][0] += hp[x];}
}int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {for(int j = 0;j <= n;j++) {dp[i][j][0] = dp[i][j][1] = 0;}}for(int i = 1;i <= n;i++) G[i].clear();for(int i = 2;i <= n;i++) {int f;scanf("%d",&f);G[f].push_back(i);}for(int i = 1;i <= n;i++) {scanf("%lld",&hp[i]);}dfs(1);for(int i = 0;i <= n;i++) {printf("%lld ",min(dp[1][i][0],dp[1][i][1]));}printf("\n");}return 0;
}

这篇关于2020ICPC 南京 Monster Hunter(树形依赖背包)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

每天认识几个maven依赖(ActiveMQ+activemq-jaxb+activesoap+activespace+adarwin)

八、ActiveMQ 1、是什么? ActiveMQ 是一个开源的消息中间件(Message Broker),由 Apache 软件基金会开发和维护。它实现了 Java 消息服务(Java Message Service, JMS)规范,并支持多种消息传递协议,包括 AMQP、MQTT 和 OpenWire 等。 2、有什么用? 可靠性:ActiveMQ 提供了消息持久性和事务支持,确保消

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

uva 10130 简单背包

题意: 背包和 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能

多重背包转换成0-1背包

http://acm.hdu.edu.cn/showproblem.php?pid=2191 多重背包特点: 一种物品有C个(既不是固定的1个,也不是无数个) 优化的方法: 运用神奇的二进制,进行物品拆分,转化成01背包 物品拆分,把13个相同的物品分成4组(1,2,4,6) 用这4组可以组成任意一个1~13之间的数! 原理:一个数总可以用2^