bzoj 4446: [Scoi2015]小凸玩密室【树形dp】

神仙题！参考https://www.cnblogs.com/wfj2048/p/7695711.html

注意完全二叉树不是满二叉树！！！！

设g[u][j]为u遍历完子树到深度为i-1的祖先的兄弟的最小花费，f[u][i]为u遍历完子树到深度为i的祖先的最小花费，显然g的作用是更新f

当u为叶子的时候，g直接用长度*点权更新即可，否则就是从先走左儿子或者先走右儿子中取min，也就是g[u][i]=min(a[ls]*b[ls]+g[ls][de[u]+1]+g[rs][i],a[rs]*b[rs]+g[rs][de[u]+1]+g[ls1][i])，然后这里有一个特殊情况，是u下面只有n一个儿子，那么就只用直接转移左儿子即可

f同理

#include<iostream>

#include<cstdio>

using namespace std;

const int N=200005;

int n,de[N];

long long a[N],b[N],f[N][20],g[N][20],dis[N],ans;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int main()

{

	n=read();

	for(int i=1;i<=n;i++)

		a[i]=read();

	de[1]=1;

	for(int i=2;i<=n;i++)

		b[i]=read(),de[i]=de[i>>1]+1,dis[i]=dis[i>>1]+b[i];

	for(int u=n;u>=1;u--)

		for(int i=2;i<=de[u];i++)

		{

			if((u<<1)>n)

				g[u][i]=(dis[u]+dis[(u>>(de[u]-i))^1]-2*dis[u>>(de[u]-i+1)])*a[(u>>(de[u]-i))^1];

			else if((u<<1)==n)

				g[u][i]=a[n]*b[n]+g[n][i];

			else

				g[u][i]=min(a[u<<1]*b[u<<1]+g[u<<1][de[u]+1]+g[u<<1|1][i],a[u<<1|1]*b[u<<1|1]+g[u<<1|1][de[u]+1]+g[u<<1][i]);

		}

	for(int u=n;u>=1;u--)

		for(int i=0;i<=de[u];i++)

		{

			if((u<<1)>n)

				f[u][i]=i?(dis[u]-dis[u>>(de[u]-i)])*a[u>>(de[u]-i)]:0;

			else if((u<<1)==n)

				f[u][i]=a[n]*b[n]+f[n][i];

			else

				f[u][i]=min(a[u<<1]*b[u<<1]+g[u<<1][de[u]+1]+f[u<<1|1][i],a[u<<1|1]*b[u<<1|1]+g[u<<1|1][de[u]+1]+f[u<<1][i]);

		}

	ans=f[1][0];

	for(int i=2;i<=n;i++)

	{

		long long nw=f[i][de[i]-1];

		for(int x=i;x>1;x>>=1)

			nw+=(x^1)>n?(a[x>>2]*b[x>>1]):(a[x^1]*b[x^1]+f[x^1][de[x>>1]-1]);

		ans=min(ans,nw);

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

bzoj 4446: [Scoi2015]小凸玩密室【树形dp】

最新文章

热门文章