BZOJ4446 [Scoi2015]小凸玩密室 【树形Dp】

时间:2022-06-24 01:47:53

题目

小凸和小方相约玩密室逃脱,这个密室是一棵有n个节点的完全二叉树,每个节点有一个灯泡。点亮所有灯

泡即可逃出密室。每个灯泡有个权值Ai,每条边也有个权值bi。点亮第1个灯泡不需要花费,之后每点亮4

个新的灯泡V的花费,等于上一个被点亮的灯泡U到这个点V的距离Du,v,乘以这个点的权值Av。在点灯

的过程中,要保证任意时刻所有被点亮的灯泡必须连通,在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们,逃出密室的最少花费是多少。

输入格式

第1行包含1个数n,代表节点的个数

第2行包含n个数,代表每个节点的权值ai。(i=l,2,…,n)

第3行包含n-l个数,代表每条边的权值bi,第i号边是由第(i+1)/2号点连向第i+l号点的边。

(i=l,2...N-1)

输出格式

输出包含1个数,代表最少的花费。

输入样例

3

5 1 2

2 1

输出样例

5

提示

对于100%的数据,1≤N≤2×105,1<Ai,Bi≤10^5

题解

首先,此题有一些比较重要的性质:

①这棵树是一棵完全二叉树

②每次要处理完一个子树才能往祖先节点处理

③所有时刻点亮的点必须联通

④初始可以从任意点开始点亮

由这些性质,我们会发现从一个节点出发,整棵树被点亮的顺序是比较固定的,

点亮一个点u,然后点亮其子树

然后再点亮u的父亲,然后点亮u的兄弟的子树

然后点亮u父亲的父亲,点亮u父亲的父亲的兄弟的子树

BZOJ4446 [Scoi2015]小凸玩密室  【树形Dp】

像这样

设\(g[i][j]\)表示从\(i\)节点开始,点亮\(i\)所在子树,然后点亮\(i\)位于第\(j\)层的祖先的最小费用

如果我们知道\(g[i][j]\),就可以枚举出发点,然后模拟上图的过程算出最后的代价

现在问题转化为如何求\(g[i][j]\)

考虑树形dp的模式

对于节点u,我们想要求出\(g[u][j]\)

①u为叶子节点,直接计算到\(j\)层祖先的价值,如果该祖先为v,则\(g[u][j] = (d[u] - d[v])*a[v]\)【d[u]指到根距离】

②u只有一个儿子,记为s,当然是\(g[u][j] = b[s] * a[s] + g[s][j]\)

③u有两个儿子

此时有两种选择:

1°先走左子树,然后走到右子树,再走到\(j\)层的父亲

2°先走右子树,然后走到左子树,再走到\(j\)层的父亲

对于两种选择,我们求出最小者

诶?等等,走到父亲的花费就是\(g\),但走到兄弟的花费呢?

我们记\(f[i][j]\)表示从节点\(i\)访问其子树并走到第\(j\)层的兄弟的最小花费

那么这两种选择就可以写成:

\(min(b[ls] * a[ls] + f[ls][dep[rs]] + g[rs][j],
b[rs] * a[rs] + f[rs][dep[ls]] + g[ls][j])\)

现在问题就转化成了求\(f[i][j]\)

用同样的思想,我们对节点u有:

①如果u为叶子节点,可以直接求出其\(f[i][j] = dis * a[v]\)

②如果u只有一个儿子,记为s,\(f[i][j] = b[s] * a[s] + f[s][j]\)

③u有两个儿子,

同样有两种类似的选择

\(min(b[ls] * a[ls] + f[ls][dep[rs]] + f[rs][j],
b[rs] * a[rs] + f[rs][dep[ls]] + f[ls][j])\)

那么这样,这题我们就做完啦

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u]; k; k = ed[k].nxt)
using namespace std;
const int maxn = 200005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}
return out * flag;
}
LL g[maxn][20],f[maxn][20];
LL n,a[maxn],b[maxn],d[maxn],dep[maxn];
void cal(){
for (int i = n; i; i--){
int ls = i << 1,rs = i << 1 | 1;
for (int j = dep[i]; j; j--){
int s = (i >> (dep[i] - j)) ^ 1,fa = s >> 1;
if (ls > n) f[i][j] = (d[i] - d[fa] + b[s]) * a[s];
else if (rs > n) f[i][j] = a[ls] * b[ls] + f[ls][j];
else f[i][j] = min(
a[ls] * b[ls] + f[ls][dep[ls]] + f[rs][j],
a[rs] * b[rs] + f[rs][dep[rs]] + f[ls][j]
);
}
}
for (int i = n; i; i--){
int ls = i << 1,rs = i << 1 | 1;
if (ls > n) g[i][0] = 0;
else if (rs > n) g[i][0] = a[ls] * b[ls] + g[ls][0];
else g[i][0] = min(
a[ls] * b[ls] + f[ls][dep[ls]] + g[rs][0],
a[rs] * b[rs] + f[rs][dep[rs]] + g[ls][0]
);
for (int j = dep[i] - 1; j; j--){
int fa = (i >> (dep[i] - j));
if (ls > n) g[i][j] = (d[i] - d[fa]) * a[fa];
else if (rs > n) g[i][j] = a[ls] * b[ls] + g[ls][j];
else g[i][j] = min(
a[ls] * b[ls] + f[ls][dep[ls]] + g[rs][j],
a[rs] * b[rs] + f[rs][dep[rs]] + g[ls][j]
);
}
}
}
void solve(){
LL ans = g[1][0];
for (int i = 2; i <= n; i++){
LL cost = g[i][dep[i] - 1];
int x,fa;
for (int u = i; u > 1; u >>= 1){
x = u ^ 1; fa = u >> 1;
if (x > n) cost += b[fa] * a[fa >> 1];
else cost += a[x] * b[x] + g[x][dep[fa] - 1];
}
ans = min(ans,cost);
}
printf("%lld\n",ans);
}
int main(){
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 2; i <= n; i++) b[i] = read();
dep[1] = 1;
for (int i = 1; i <= n; i++){
if ((i << 1) <= n){
dep[i << 1] = dep[i] + 1;
d[i << 1] = d[i] + b[i << 1];
}
if ((i << 1 | 1) <= n){
dep[i << 1 | 1] = dep[i] + 1;
d[i << 1 | 1] = d[i] + b[i << 1 | 1];
}
}
cal();
solve();
return 0;
}

BZOJ4446 [Scoi2015]小凸玩密室 【树形Dp】的更多相关文章

  1. &lbrack;BZOJ4446&rsqb;SCoi2015 小凸玩密室 树形DP&lpar;烧脑高能预警&rpar;

    4446: [Scoi2015]小凸玩密室 Time Limit: 10 Sec  Memory Limit: 128 MB Description 小凸和小方相约玩密室逃脱,这个密室是一棵有n个节点 ...

  2. BZOJ4446&colon;&lbrack;SCOI2015&rsqb;小凸玩密室&lpar;树形DP&rpar;

    Description 小凸和小方相约玩密室逃脱,这个密室是一棵有n个节点的完全二叉树,每个节点有一个灯泡.点亮所有灯泡即可逃出密室. 每个灯泡有个权值Ai,每条边也有个权值bi.点亮第1个灯泡不需要 ...

  3. LUOGU P4253 &lbrack;SCOI2015&rsqb;小凸玩密室&lpar;树形dp&rpar;

    传送门 解题思路 玄学树形\(dp\),题目描述极其混乱...看错了两次题,设首先根据每次必须点完子树里的灯才能点别的,那么点灯情况只有两种,第一种是点到某一个祖先,第二种是点到某一个祖先的兄弟.所以 ...

  4. BZOJ&period;4446&period;&lbrack;SCOI2015&rsqb;小凸玩密室&lpar;树形DP&rpar;

    BZOJ LOJ 洛谷 (下面点亮一个灯泡就说成染色了,感觉染色比较顺口... 注意完全二叉树\(\neq\)满二叉树,点亮第一个灯泡\(\neq\)第一次点亮一号灯泡,根节点应该就是\(1\)... ...

  5. 2019&period;03&period;26 bzoj4446&colon; &lbrack;Scoi2015&rsqb;小凸玩密室(树形dp)

    传送门 题意简述: 给一棵完全二叉树,有点权aia_iai​和边权,每个点有一盏灯,现在要按一定要求点亮: 任意时刻点亮的灯泡必须连通 点亮一个灯泡后必须先点亮其子树 费用计算如下:点第一盏灯不要花费 ...

  6. BZOJ4446 SCOI2015小凸玩密室(树形dp)

    设f[i][j]为由根进入遍历完i子树,最后一个到达的点是j时的最小代价,g[i][j]为由子树内任意一点开始遍历完i子树,最后一个到达的点是j时的最小代价,因为是一棵完全二叉树,状态数量是nlogn ...

  7. BZOJ4446&colon; &lbrack;Scoi2015&rsqb;小凸玩密室

    用ui,j表示走完i的子树后走到i的深度为j的祖先的兄弟的最小代价: 用vi,j表示走完i的子树后走到i的深度为j的祖先的最小代价,用u算出v. 枚举起点,计算答案. #include<bits ...

  8. &lbrack;bzoj4446&rsqb; &lbrack;loj&num;2009&rsqb; &lbrack;Scoi2015&rsqb; 小凸玩密室

    Description 小凸和小方相约玩密室逃脱,这个密室是一棵有 \(n\) 个节点的完全二叉树,每个节点有一个灯泡.点亮所有灯泡即可逃出密室.每个灯泡有个权值 \(Ai\) ,每条边也有个权值 \ ...

  9. bzoj 4446&colon; &lbrack;Scoi2015&rsqb;小凸玩密室

    Description 小凸和小方相约玩密室逃脱,这个密室是一棵有n个节点的完全二叉树,每个节点有一个灯泡.点亮所有灯 泡即可逃出密室.每个灯泡有个权值Ai,每条边也有个权值bi.点亮第1个灯泡不需要 ...

随机推荐

  1. Android 更新UI的几种方式

    1.Activity的 runOnUiThread textView = (TextView) findViewById( R.id.tv ); new Thread(new Runnable() { ...

  2. latex 异或

    用\lxor \(\lxor\) 用\veebar \(\veebar\) 用\oplus \(\oplus\) ... 怎么不是我想象的那样... 算了.

  3. awstats 日志分析工具linux下的安装和使用

    合并日志文件可以使用 bash 的sort命令: -o log_all access*.log 也可以使用  awstats 提供的 logresolvemerge.pl -showsteps acc ...

  4. HDU 2065 &OpenCurlyDoubleQuote;红色病毒”问题 --指数型母函数

    这种有限制的类棋盘着色问题一般可以用指数型母函数来解决,设Hn表示这样的着色数,首先H0=1,则Hn等于四个字母的(A,B,C,D)的多重集合的n排列数,其中每个字母的重数是无穷,且要求A,C出现的次 ...

  5. JavaWeb学习总结(一)—JavaWeb开发入门及环境搭建

    一.基本概念 1.1.软件体系结构 1.C/S:Client/Servlet,例如QQ就是CS结构需要编写服务器端程序和客户端程序.缺点:更新需要两端,总要求客户下载新的客户端程序优点:安全性比较好2 ...

  6. &lbrack;视频&rsqb;MAC OS 技巧之如何更新及重装MAC系统

    mac os是当今最好用的桌面操作系统,但再好的系统也有新版本发布的一天,或者被极客的你尝试各种设置而配置混乱了,这时我们就要进行系统更新或者重装了. 系统更新 Mac OS有新版本推出时,会自动在A ...

  7. spring中Bean的注入参数详解

    字面值    一般指可用字符串表示的值,这些值可以通过<value>元素标签进行注入.在默认情况下,基本数据类型及其封装类.String等类型都可以采取字面值注入的方式,Spring容器在 ...

  8. Python 调用C&plus;&plus;

    1.C++代码提供Python需要的接口: #include "stdafx.h" #include <boost/python.hpp> #include <s ...

  9. T-SQL事务

    事务 订火车票的时候,下一个订单,这个订单中,包含多个购买信息,要么全部执行,要么全部不执行,合作事务就是来处理这种模型的一种机制. --关键字:transaction 或 tran 简写形式 --开 ...

  10. freemarker常见语法大全

    推荐freemarker系列教程:http://swiftlet.net/archives/category/freemarker FreeMarker的插值有如下两种类型:1,通用插值${expr} ...