洛谷P3574 [POI2014] FAR-FarmCraft(树形dp)

2024-05-26 11:20

本文主要是介绍洛谷P3574 [POI2014] FAR-FarmCraft(树形dp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

洛谷 P 3574 [ P O I 2014 ] F A R − F a r m C r a f t (树形 d p ) \Huge{洛谷P3574 [POI2014] FAR-FarmCraft(树形dp)} 洛谷P3574[POI2014]FARFarmCraft(树形dp

文章目录

  • 题意
    • 题目说明
  • 思路
  • 标程

题目链接:P3574 [POI2014] FAR-FarmCraft - 洛谷

题意

给出 n n n个节点、 n − 1 n-1 n1条边的一棵无根树;经过每条边所用时间都为 1 1 1。然后每个节点都有点权 b [ i ] b[i] b[i]

题目故事:管理员从自己家(一号节点)出发,然后将一批电脑分发给每个节点的居民,每个居民得到电脑后会立即开始下载游戏,下载游戏的时间为点权 b [ i ] b[i] b[i]

管理员每次经过某节点就相当于直接分发给居民。

管理员的车恰好能够走每条路两遍。

要求计算出管理员从开始配送到所有居民都能玩上游戏所用最少时间。

题目说明

给一棵树,走过每条边需要花费一个时间,安装软件又需要花费一个时间,需要遍历整棵树并回到起点,想让所有点中到达时间+安装时间的最大值最小,问这个值是多少?

思路

跟据题目要求,显然能够知道,题目要求求出所有居民中最后玩上游戏的居民所用时间,并且要求这个时间最小。

跟据题目说明,我们可以想到:对于同一个节点的子节点,大致的贪心思路是先遍历点权最大的节点

但是可能会出现一种情况(画的比较丑陋,多多见谅):
在这里插入图片描述

但是我们可以注意到题目有限制条件**“管理员的车恰好能够走每条路两遍”**,那么我们就不用考虑这种情况了。

一般地,我们用 f [ i ] f[i] f[i]表示节点 i i i这棵子树中的最大值 d e p [ i ] dep[i] dep[i]表示从节点 i i i出发遍历其子树并返回所用的总时间 b [ i ] b[i] b[i]表示点权

容易发现,这道题属于树形dp中的选择节点型,只不过需要判断的是选择子节点的先后顺序。

那么对应的状态转移方程即为:
f [ x ] = max ⁡ ( f [ x ] , d e p [ x ] + max ⁡ ( f [ i ] , f [ j ] + d e p [ i ] + 2 ) + 1 ) f[x]=\max(f[x], dep[x]+\max(f[i],f[j]+dep[i]+2)+1) f[x]=max(f[x],dep[x]+max(f[i],f[j]+dep[i]+2)+1)
其中 x x x为当前节点, i , j i,j i,j表示它的其中两个子节点。需要解释一下:

  • 方程中的+2是因为从一个子节点到另一个子节点的两段路。
  • 方程中的+1是因为从 x x x节点到子节点的一段路。

但是该这样进行状态转移,我们需要对子节点相互比较,其时间复杂度为 O ( n 2 ) O(n^2) O(n2),会超时。

我们考虑优化状态转移方程:

  • 如果先 i i i j j j max ⁡ ( f [ i ] , f [ j ] + d e p [ i ] + 2 ) \max(f[i],f[j]+dep[i]+2) max(f[i],f[j]+dep[i]+2)

  • 如果先 j j j i i i max ⁡ ( f [ j ] , f [ i ] + d e p [ j ] + 2 ) \max(f[j],f[i]+dep[j]+2) max(f[j],f[i]+dep[j]+2)

  • 因为 f [ i ] < f [ i ] + d e p [ j ] + 2 f[i] <f[i]+dep[j]+2 f[i]<f[i]+dep[j]+2 f [ j ] < f [ j ] + d e p [ i ] + 2 f[j]<f[j]+dep[i]+2 f[j]<f[j]+dep[i]+2

  • 原式可化为: max ⁡ ( f [ j ] + d e p [ i ] + 2 , f [ i ] + d e p [ j ] + 2 ) \max(f[j]+dep[i]+2,f[i]+dep[j]+2) max(f[j]+dep[i]+2,f[i]+dep[j]+2)

  • 即为: f [ i ] − d e p [ i ] < f [ j ] − d e p [ j ] f[i]-dep[i]<f[j]-dep[j] f[i]dep[i]<f[j]dep[j](当选 j j j时成立)

因此在判断选取子节点时,可以先对子节点按照上述不等式排序,即为选取子节点的先后顺序。

最后需要注意的是,dfs过程中我们并没有判断根节点的时间,需要输出时进行判断取 m a x max max

标程

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long 
#define ULL unsigned long long 
#define PII pair<int, int>
#define lowbit(x) (x & -x)
#define Mid ((l + r) >> 1)
#define ALL(x) x.begin(), x.end()
#define endl '\n'
#define fi first 
#define se secondconst int INF = 0x7fffffff;
const int Mod = 1e9 + 7;
const int N = 5e5 + 10;int n;
vector<int> a[N];
int b[N], dep[N], f[N];void dfs(int x, int y) {if(x != 1) f[x] = b[x];for(auto i : a[x]) {if(i == y) continue;dfs(i, x);}sort(ALL(a[x]), [](int n1, int n2) {return dep[n1] - f[n1] < dep[n2] - f[n2];});for(auto i : a[x]) {if(i == y) continue;f[x] = max(f[x], f[i] + dep[x] + 1);dep[x] += dep[i] + 2;}
}void Solved() {cin >> n;for(int i = 1; i <= n; i ++ ) {cin >> b[i];}for(int i = 1; i < n; i ++ ) {int x, y; cin >> x >> y;a[x].push_back(y); a[y].push_back(x);}dfs(1, 0);cout << max(f[1], dep[1] + b[1]) << endl;
}signed main(void) {IOSint ALL = 1; // cin >> ALL;while(ALL -- ) Solved();// cout << fixed;//强制以小数形式显示// cout << setprecision(N); //保留n位小数return 0;
}

这篇关于洛谷P3574 [POI2014] FAR-FarmCraft(树形dp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

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

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

uva 10118 dP

题意: 给4列篮子,每次从某一列开始无放回拿蜡烛放入篮子里,并且篮子最多只能放5支蜡烛,数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时,猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs

uva 10069 DP + 大数加法

代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl

uva 10029 HASH + DP

题意: 给一个字典,里面有好多单词。单词可以由增加、删除、变换,变成另一个单词,问能变换的最长单词长度。 解析: HASH+dp 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o