作者:全都变了吗 | 来源:互联网 | 2023-06-21 11:41
题目链接题意给出一个具有n个节点的树,每个节点都有一个权值w,现在对于每个节点s要求出一个$f(s)$对于节点s,找到一个节点序列,\(v_1,v_2,v_3v_m\),\(
题目链接
题意
给出一个具有 n 个节点的树,每个节点都有一个权值 w,现在对于每个节点 s 要求出一个\(f(s)\)
- 对于节点 s,找到一个节点序列,\(v_1,v_2,v_3...v_m\),\(v_1 = s\),\(v_{i+1}\)是\(v_i\)的祖先节点
- \(f(s)=w_s+\sum_{i=2}^{m}{w_{v_i}\ opt\ w_{v_{i-1}}} f(s) 要尽可能的大\)
输出\(\sum_{i=1}^n i*f(i)\)
思路
我们用 \(dp[i]\) 表示\(f(i)-w_i\)
先不考虑树上,把题目转移到一个整数数组上来。
那么 \(dp[i]=max(dp[i],dp[j]+w_j\ opt \ \ w_i)(j
树上同理,但是这个转移方程的复杂度太高了。
愣是想不到如何把 \(O(n^2)\) 变成 \(O(logn)\)。
看题解发现是真滴骚。
![技术图片](https://img.php1.cn/3cd4a/1eebe/cd5/60405fda58cd0acd.webp)
在我理解来,就是把遍历 \(j\) 的过程变成了遍历 \(w_j\) 的可能取值,但是 \(w_j\) 有 \(2^{16}\)种情况,也不可能遍历,我们通过一个数组 \(f[a][b]\) 变得只需枚举 \(2^8\) 来降低复杂度 。
总体复杂度为 \(N*2^8\)即\(2^{24}\)
代码
/*
* @Autor: valk
* @Date: 2020-08-11 12:38:37
* @LastEditTime: 2020-09-28 17:19:07
* @Description: 如果邪恶 是华丽残酷的乐章 它的终场 我会亲手写上 晨曦的光 风干最后一行忧伤 黑色的墨 染上安详
*/
#include
#include
#include
【HDU】5735 Born Slippy DP+折半枚举优化