P4253 [SCOI2015]小凸玩密室

标签：rs int ++ ls 小凸 SCOI2015 P4253 dp dis

首先分析题意：

给定一棵完全二叉树及其点权与边权

现在从某个节点出发，之后遍历整棵二叉树，要求

• 遍历的节点必须联通
• 遍历另一棵子树前先遍历完当前子树
• 访问x之后马上访问y（访问合法的前提下），费用为dist(x,y)*w[y]，其中dist为距离，w为点权

访问的第一个节点无需费用

要求最小化总费用

显然，这是一个贪心、暴力等做法无法解决的问题，因为求解最优子结构，我们考虑DP

---

首先，我们尝试确立阶段。

这个题乍一看貌似不好划分（常规的树形DP不好保证无后效性），但细想下来，会发现：每棵子树遍历完才会遍历另一棵，那么结尾一定会在一个叶子节点上（因为还要保证联通）

那么这就是从一个叶子节点往上退的过程。对于每个节点k，有如下情况：

1. 为叶子节点：将点亮他的某一级祖先u（u未点亮，即u在起点上方）或某一级祖先u的另一个儿子（u已点亮，即u在起点下方）
2. 为普通节点：若k未点亮，其儿子将被点亮，k在起点上方；k已点亮，那还关他毛线事啊

于是我们就可以定出三维DP数组dp[i,j,0/1]来表示一个点亮i后回到 第j个祖先/第j个祖先的另一个儿子 的最小费用。然后得到我打不出来的转移方程

没关系，用代码说明。不过在此之前，我们先给出初始化的处理部分不然怎么看

inline void init(){
	for(int i=1;i<=n;i++) w[i]=read();//点权
	for(int i=2;i<=n;i++) dis[i][1]=read();//dis[k][i]表示k到k的第i级祖先的距离
	for(int i=1;i<=(n>>1)+1;i++){//方便后面使用，先把左右儿子处理出来
		if((i<<1)<=n) ls[i]=i<<1;
		if((i<<1|1)<=n) rs[i]=i<<1|1;//注意位运算和比较的优先级。。。
	}
	for(int i=2;i<=18;i++)//i的范围是树的深度决定的，但开大了没影响
		for(int k=n;k>>i;k--)
			dis[k][i]=dis[k][i-1]+dis[k>>(i-1)][1];//此处有些类似于倍增LCA深度的预处理：
}

此外，还有一个有用的东西：

inline int bro(int k,int x){
	return (k>>(x-1))^1;//这东西的原理是一个节点的左右儿子是成对储存的，正好和xor运算的一些性质类似
}

然后我们就可以写出状态转移的代码了：

	for(int k=n;k>=1;k--)
		if(!ls[k])/*为叶子节点*/ for(int i=1;k>>(i-1)/*这里有个边界条件：是否存在k的i级祖先*/;i++) dp[k][i][1]=(dis[k][i]+dis[bro(k,i)][1])*w[bro(k,i)];//意即：从k到k第i级祖先的另一个儿子，费用为路径长度乘上点权（这里我们把路径长度拆成了两部分）
		else if(!rs[k])/*只有左儿子*/ for(int i=1;k>>(i-1);i++) dp[k][i][1]=dis[ls[k]][1]*w[ls[k]]+dp[ls[k]][i+1][1];//意即：从k访问k左儿子的费用加上k左子树整体的费用（由于k不存在右儿子，所以右儿子不会影响到答案）
		else/*两个儿子都有*/ for(int i=1;k>>(i-1);i++) dp[k][i][1]=Min/*自己写的函数要快些。。。*/(dis[ls[k]][1]*w[ls[k]]+dp[ls[k]][1][1]+dp[rs[k]][i+1][1],dis[rs[k]][1]*w[rs[k]]+dp[rs[k]][1][1]+dp[ls[k]][i+1][1]);//左边意即：从k访问k左儿子并加上费用，再加上访问右子树后折返k的第i级祖先的费用。右边同理

这段非常长的代码就是DP的第一部分，即第三维为1时，因为该部分于第三维为0的部分无关。（好吧这本来该是两个数组被我压成了1个）

接着同理可以写出第三维为0的部分的代码：

	for(int k=n;k>=1;k--)
		if(!ls[k]) for(int i=1;k>>(i-1);i++) dp[k][i][0]=dis[k][i]*w[k>>i];
		else if(!rs[k]) for(int i=1;k>>(i-1);i++) dp[k][i][0]=dp[ls[k]][i+1][0]+dis[ls[k]][1]*w[ls[k]];//上面部分是类似的
		else for(int i=1;k>>(i-1);i++) dp[k][i][0]=Min(dis[ls[k]][1]*w[ls[k]]+dp[ls[k]][1][1]+dp[rs[k]][i+1][0],dis[rs[k]][1]*w[rs[k]]+dp[rs[k]][1][1]+dp[ls[k]][i+1][0]);//这里因为从第一棵子树返回后要到另一棵子树，所以第一次用了第三维为1的情况；第二次就不到另一棵子树了，所以采用第三维为0的情况

嗯，简单又精简。

然而还没完，题目没有指定初始位置不然还求个毛线啊，我们需要小小地暴力一下：

	for(int k=1;k<=n;k++){//枚举起点
		ll now=dp[k][1][0];//回到当前子树父节点的费用
		for(int i=1,pre=k>>1;pre;i++,pre>>=1){//pre是当前的父节点
			int b=bro(k,i);//当前父节点意义下的兄弟
			if(b>n) now+=dis[pre][1]*w[pre>>1];//你没有这个兄弟，就不管了，直接算
			else now+=dis[b][1]*w[b]+dp[b][2][0];//否则加上你兄弟产生的费用
		}
		ans=Min(ans,now);//更新答案
	}

至此，本题结。

AC Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while('0'>ch||'9'<ch){if(ch=='-') f=-f;ch=getchar();}
	while('0'<=ch&&'9'>=ch)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
inline ll Min(ll x,ll y){
	return x<y?x:y;
}
const int N=2e5+5;
int n=read();
int w[N],ls[N],rs[N];
ll dis[N][20];
ll dp[N][20][2];
inline void init(){
	for(int i=1;i<=n;i++) w[i]=read();
	for(int i=2;i<=n;i++) dis[i][1]=read();
	for(int i=1;i<=(n>>1)+1;i++){
		if((i<<1)<=n) ls[i]=i<<1;
		if((i<<1|1)<=n) rs[i]=i<<1|1;
	}
	for(int i=2;i<=18;i++)
		for(int k=n;k>>i;k--)
			dis[k][i]=dis[k][i-1]+dis[k>>(i-1)][1];
}
inline int bro(int k,int x){
	return (k>>(x-1))^1;
}
inline ll calc(){
	ll ans=1e17;
	for(int k=n;k>=1;k--)
		if(!ls[k]) for(int i=1;k>>(i-1);i++) dp[k][i][1]=(dis[k][i]+dis[bro(k,i)][1])*w[bro(k,i)];
		else if(!rs[k]) for(int i=1;k>>(i-1);i++) dp[k][i][1]=dis[ls[k]][1]*w[ls[k]]+dp[ls[k]][i+1][1];
		else for(int i=1;k>>(i-1);i++) dp[k][i][1]=Min(dis[ls[k]][1]*w[ls[k]]+dp[ls[k]][1][1]+dp[rs[k]][i+1][1],dis[rs[k]][1]*w[rs[k]]+dp[rs[k]][1][1]+dp[ls[k]][i+1][1]);
	for(int k=n;k>=1;k--)
		if(!ls[k]) for(int i=1;k>>(i-1);i++) dp[k][i][0]=dis[k][i]*w[k>>i];
		else if(!rs[k]) for(int i=1;k>>(i-1);i++) dp[k][i][0]=dp[ls[k]][i+1][0]+dis[ls[k]][1]*w[ls[k]];
		else for(int i=1;k>>(i-1);i++) dp[k][i][0]=Min(dis[ls[k]][1]*w[ls[k]]+dp[ls[k]][1][1]+dp[rs[k]][i+1][0],dis[rs[k]][1]*w[rs[k]]+dp[rs[k]][1][1]+dp[ls[k]][i+1][0]);
	for(int k=1;k<=n;k++){
		ll now=dp[k][1][0];
		for(int i=1,pre=k>>1;pre;i++,pre>>=1){
			int b=bro(k,i);
			if(b>n) now+=dis[pre][1]*w[pre>>1];
			else now+=dis[b][1]*w[b]+dp[b][2][0];
		}
		ans=Min(ans,now);
	}
	return ans;
}
int main(){
	init();
	printf("%lld",calc());
	return 0;
}

不过，这篇博客不是题解。

这只是我看完题解之后的学习笔记罢了。。。

好难啊。。。

标签：rs,int,++,ls,小凸,SCOI2015,P4253,dp,dis
From： https://www.cnblogs.com/LQ636721/p/17084579.html