[SCOI2015]小凸玩密室 - A-Failure的博客

题目

题目描述

小凸和小方相约玩密室逃脱，这个密室是一棵有 $n$ 个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值 $a_i$ ，每条边也有个权值 $b_i$ 。点亮第一个灯泡不需要花费，之后每点亮一个新的灯泡 $v$ 的花费，等于上一个被点亮的灯泡 $u$ 到这个点 $v$ 的距离 $D_{u,v}$ ，乘以这个点的权值 $a_v$ 。在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。请告诉他们，逃出密室的最少花费是多少。

输入输出格式

输入格式：

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

第 $2$ 行包含 $n$ 个数，代表每个节点的权值 $a_i$ 。 $(i = 1, 2,……, n)$

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

输出格式：

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

输入输出样例

输入样例#1：

3
5 1 2
2 1

输出样例#1：

说明

对于 $10\%$ 的数据， $1 \leq n \leq 10$

对于 $20\%$ 的数据， $1 \leq n \leq 20$

对于 $30\%$ 的数据， $1 \leq n \leq 2000$

对于 $100\%$ 的数据， $1 \leq n \leq 2 * 10^5, 1 \leq a_i, b_i \leq 10^5$

题解

因为是完全二叉树，树的高度为 $\log n$

设 $f_{i,j}$ 表示搞了点 $i$ 最后到 $i$ 的深度为 $j$ 的祖先需要的最少花费， $g_{i,j}$ 表示搞了点 $i$ 最后到 $i$ 的深度为 $j$ 的祖先的兄弟需要的最小花费

转移就从叶子一路转移上去即可

最后枚举起始点，统计一路跳到根的花费

因为这个题的树的构造很有特点，所以可以不用建树，用位运算搞搞各个点的关系就出来了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (i<<1)
# define tr (i<<1|1)
# define F (i>>d[i]-j)
# define LL long long
using namespace std;
const int MAX=2e5+5;
int n;
LL ans=1e18,Ans;
int d[MAX],a[MAX],b[MAX],D[MAX];
LL f[20][MAX],g[20][MAX];
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
void GET_DP()
{
	for(int i=n;i>=1;--i)
	  for(int j=0;j<19;++j)
	    if(tl>n) f[j][i]=1ll*(D[i]-D[F])*a[F],g[j][i]=1ll*(D[i]-D[F]+b[F]+b[F^1])*a[F^1];
	    else if(tl==n) f[j][i]=1ll*a[tl]*b[tl]+f[j][tl],g[j][i]=1ll*a[tl]*b[tl]+g[j][tl];
	    else f[j][i]=min(1ll*a[tl]*b[tl]+g[d[tl]][tl]+f[j][tr],1ll*a[tr]*b[tr]+g[d[tr]][tr]+f[j][tl]),g[j][i]=min(1ll*a[tl]*b[tl]+g[d[tl]][tl]+g[j][tr],1ll*a[tr]*b[tr]+g[d[tr]][tr]+g[j][tl]);
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	  a[i]=read();
	for(int i=2;i<=n;++i)
	  b[i]=read();
	for(int i=1;i<=n;++i)
	  d[i]=d[i>>1]+1,D[i]=D[i>>1]+b[i];
	GET_DP();
	for(int x=1;x<=n;++x)
	  {
	  	Ans=f[d[x]-1][x];
	  	for(int i=x;i>1;i>>=1)
	  	  if((i^1)>n) Ans+=1ll*b[i>>1]*a[i>>2];
	  	  else Ans+=d[i^1]<2?0:f[d[i^1]-2][i^1]+1ll*b[i^1]*a[i^1];
	  	ans=min(ans,Ans);
	  }
	return printf("%lld",ans),0;
}

题目