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

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

神仙题!参考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】的更多相关文章

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

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

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

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

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

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

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

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

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

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

  6. BZOJ 4443&colon; &lbrack;Scoi2015&rsqb;小凸玩矩阵 最大流

    4443: [Scoi2015]小凸玩矩阵 题目连接: http://www.lydsy.com/JudgeOnline/problem.php?id=4443 Description 小凸和小方是好 ...

  7. bzoj 4443 &lbrack;Scoi2015&rsqb;小凸玩矩阵 网络流&comma;二分

    [Scoi2015]小凸玩矩阵 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1564  Solved: 734[Submit][Status][Di ...

  8. BZOJ4446 &lbrack;Scoi2015&rsqb;小凸玩密室 【树形Dp】

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

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

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

随机推荐

  1. Web API接口之Geolocation

    0.关于Geolocation Geolocation,地理位置API.用于获取用户的位置信息.它不算是现有的HTML5标准的“直系”成员,但是是W3C的一个标准.它几乎就是一个真正的JavaScri ...

  2. Lind&period;DDD&period;Domain&period;IOwnerBehavor对实体的意义

    回到目录 对于Lind.DDD架构,我之前写了不少文章,对于它的Domain模式也介绍了不少,像之前的IEntity,ILogicDeleteBehavor,IModifyBehavor,IStatu ...

  3. IOS开发-项目实战-点赞功能的实现

    实现思路: 1.每一条新闻就是一个cell,在cell上添加点赞按钮. 2.让cell的控制器成为自定义cell的代理,将点击了哪一个cell放在代理方法中传出去. 3.并将这条新闻的ID和当前用户的 ...

  4. loadrunner负载测试实例

    回想起第一次做性能测试,感慨万千,故写下本文,从:设置虚拟用户,设置场景以及分析运行结果三个方面进行阐述 硬件环境:硬盘 1TG,cpu 3.40GHz,内存4G 软件环境:IE9.0,Weblogi ...

  5. JSP内置标签 JSP中JavaBean标签 JSP开发模式 EL和JSTL快速入门

    2 JSP内置标签(美化+业务逻辑)   1)为了取代<%%>脚本形式,使用JSP标签/JSP动作,目的:与JSP页面的美化,即JSP面页都是由标签组成,不再有其它的内容   2)JSP内 ...

  6. 【制作镜像Win&ast;】特殊配置

    下载disk.config: wget http://10.254.3.75/images/configdrive/disk.config 修改libvirt.xml,更换cdrom为disk.con ...

  7. MongoDB初探-基本语句和数据结构

    MySQL: 1 金老板 18 15512351234 2 小哪吒 20 15312341234 3 Alex 73 15512341234 MongoDB: { { id : 1, name:金老板 ...

  8. 微信小程序之 真机键盘弹窗遮盖input框

    正常效果: 问题效果: 发现这个问题后呢,我先去看了api,api上是这么说的 哦吼~ 然后我也不知道是不是我的打开方式不对还是什么~~ 没有效果~~  那怎么办呢~~  换方法呗~~ 我只好用这个方 ...

  9. ansible中常用模块详解

    ansible中常用的模块详解: file模块 ansible内置的可以查看模块用法的命令如下: [root@docker5 ~]# ansible-doc -s file - name: Sets ...

  10. apache&plus;php windows下配置

    2014年1月9日 13:58:54 现在PHP大部分是vc9编译的,其扩展在windows下大部分也都是用vc9编译的(memcache,xdebuge...),,所以要想Apache+PHP+PH ...