4446: [Scoi2015]小凸玩密室
Time Limit:&10 Sec&&Memory Limit:&128 MB
Description
小凸和小方相约玩密室逃脱，这个密室是一棵有n个节点的完全二叉树，每个节点有一个灯泡。点亮所有灯
泡即可逃出密室。每个灯泡有个权值Ai，每条边也有个权值bi。点亮第1个灯泡不需要花费，之后每点亮4
个(1个)新的灯泡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个数，代表最少的花费。
Sample Input
Sample Output
对于100%的数据，1&N&2&105，1&Ai,Bi&10^5
（其实我是回来补暑假没写完的题解的）
(首先我经过激烈的思想斗争,认为那个点亮灯泡的花费计算只与上一个有关(其实是因为前4个太难考虑了...)
事实证明这样做是对的..就是只考虑上一个:(
有了之前做非线性DP的经验,我一开始想的还是合并类型
但是发现数据范围不太对....这似乎是一个介于O(n)和O(n2)范围内的DP
我们考虑怎么定义状态,以及怎么转移.
一开始我想的是f[i][j]表示"走完以i为根的子树之后走去j点的最小花费"
但是我发现这个MLE了,2e5开不下
但是这又是一颗完全二叉树,所以我们考虑能不能应用他的一些性质
我们观察到,点灯泡的起点没有确定,但是题目有这样的两个限制:
要保证任意时刻所有被点亮的灯泡必须连通.
在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡
这样的话,某一个点被点亮的时候只能有三种转移的情况:从儿子走来,从兄弟走来和从父亲走来(废话)
因此,当某一个子树被完全点亮之后,我们就要去某一个他的祖先,或者是他某个祖先的儿子
我们发现上面这两个都与这个节点的祖先有关（这里我们把自己也看成自己的祖先）
由于这是一棵二叉树,我们完全可以通过位运算(左移,右移和异或)来计算出某个节点的某个深度的祖先.
这样,第二维完全不用是O(n)的:我们可以把第二维设为深度,即走完以i为根的子树之后走去深度为j的祖先节点的&XXXX&的最小花费
那么我们再考虑一下：我们这个点的祖先节点可能已经被点亮，也可能没有被点亮。如果已经点亮，我们就必须去点亮祖先的兄弟那棵子树。
因此我们定义两个数组：
f(ather)[i][j]表示走完以i为根的子树之后去点亮深度为j的祖先节点的最小花费
b(rother)[i][j]表示走完以i为根的子树之后去点亮深度为j的祖先节点的兄弟节点的最小花费
接下来我们考虑状态的转移。最好想到的是节点i是叶子节点的情况：直接走去对应的节点即可。
我们再考虑下一种情况：只有一个儿子。那么此时我们必须先走到这个儿子，然后再从这个儿子走去对应的节点。
如果有2个儿子，我们应该考虑两种情况，即先去左儿子还是先去右儿子，然后取较小值，并累加中间的权值。
这样，转移部分就被我们解决了。具体代码实现就是上面这个思路的体现。
最后，我们再来考虑&第一个灯泡不确定&这个条件
假设第一步点亮了灯泡u，设它的兄弟为bro(ther)，那么接下来我们应该一步一步往上爬，直到点亮所有灯泡。
也就是说重复u-&fa-&bro-&fa-&bro-&......这个过程
我们只需要模拟这个过程，就可以得到第一步点亮u的最小花费（记得讨论bro不存在的情况）
然后在所有最小值里取最小即可。
这道题的思维含量很高，是一道不可多得的好题呀！
完整代码见下：
1 #include &cstdio&
2 #include &cstring&
3 #include &algorithm&
4 using namespace
5 const int N=200010;
6 typedef long long LL;
7 int n,l[N],r[N],deep[N];
8 LL f[N][19],b[N][19],a[N],lval[N],rval[N],dis[N];
9 int main()
scanf("%d",&n);LLintdeep[1]=1;
for(int i=1;i&=n;i++)scanf("%lld",&a[i]);
for(int i=1;i&n;i++)
scanf("%lld",&v);
rt=(i+1)&&1,deep[i+1]=deep[rt]+1;
if((i+1)&1) r[rt]=i+1,rval[rt]=v,dis[r[rt]]=dis[rt]+rval[rt];
else l[rt]=i+1,lval[rt]=v,dis[l[rt]]=dis[rt]+lval[rt];
for(int i=n;i&1;i--)
for(int j=2;j&=deep[i];j++)
int fa=i&&(deep[i]-j+1),fab=(i&&(deep[i]-j))^1;
b[i][j]=( dis[i]+dis[fab]-(dis[fa]&&1) )*a[fab];
else b[i][j]=lval[i]*a[l[i]]+b[l[i]][j];
else b[i][j]=min(lval[i]*a[l[i]]+b[l[i]][deep[i]+1]+b[r[i]][j],rval[i]*a[r[i]]+b[r[i]][deep[i]+1]+b[l[i]][j]);
for(int i=n;i;i--)
for(int j=0;j&=deep[i];j++)
if(!j)f[i][j]=0;
int fa=i&&(deep[i]-j);
f[i][j]=(dis[i]-dis[fa])*a[fa];
else f[i][j]=lval[i]*a[l[i]]+f[l[i]][j];
else f[i][j]=min(lval[i]*a[l[i]]+b[l[i]][deep[i]+1]+f[r[i]][j],rval[i]*a[r[i]]+b[r[i]][deep[i]+1]+f[l[i]][j]);
LL ans=f[1][0];
for(int i=2;i&=n;i++)
int u=i,bro=u^1;
LL tmp=f[u][deep[u]-1];
while(u&1)
if(bro&n)tmp+=a[u&&2]*(dis[u&&1]-dis[u&&2]);
else tmp+=a[bro]*(dis[bro]-dis[u&&1])+f[bro][deep[u&&1]-1];
u&&=1,bro=u^1;
ans=min(ans,tmp);
printf("%lld\n",ans);
阅读(...) 评论()比狼人杀更烧脑，比密室还刺激！这款真人推理游戏目测要火遍杭州！
狼人杀烧脑？
密室逃脱刺激？
那么你肯定是还没有玩过
来自【棋士桌游推理馆】
更烧脑、更刺激的
全！民！大！侦！探！
（图片来源：棋士桌游推理馆）
看着好像有点惊悚？
没错了，因为这款真人推理游戏
又被称为：◤谋杀之谜◥
MMG（Murder Mystery Game）
（图片来源：棋士桌游推理馆）
简单来说，
MMG就是通过角色扮演一起破案！
每局游戏都起源于一宗谋杀案，
参与游戏的玩家均在案发现场，
当然，凶手也在其中...
每位玩家拥有相应的身份，
阅读完属于自己的剧本后开始角色扮演。
通过调查房间内的线索，
以及彼此之间的交谈和试探，
推理案情的真相，
找出真凶...
（图片来源：棋士桌游推理馆）
机智的小伙伴可能已经发现了：
这不就是《明星大侦探》的同款游戏吗！
注：湖南卫视的一档真人秀节目，
由几位明星嘉宾共同参与破案。
不清楚的小伙伴可自行百度哦...
以前只能看不能玩，
现在只要去城西的【棋士桌游推理馆】，
就可以玩这款烧脑的推理游戏啦！
（图片来源：棋士桌游推理馆）
上周，小编就和小伙伴去体验了一番！主题是【董事长杀人事件】。
故事讲得是某集团的董事长死在了自己家中的床上，案发现场的一干人等——董事长的独生子、保镖、公司财务、私人医生、黑帮老大、黑帮夫人都有嫌疑，他们各有各的秘密，又相互牵连，到底谁是凶手呢？？？
这个答案，需要大家通过讨论和调查找出来！
（剧照先来一发！图片来源：城西生活圈）
首先，在了解完大概的剧情之后，我们可以根据自己的喜好挑选角色，然后会拿到一份相对应的剧本。记住，看剧本的时候不要让别人看到哦，因为每个角色都藏着几个不可告人的秘密......
（有种进军演艺圈的赶脚啊...图片来源：城西生活圈）
这里再顺便说一下游戏玩法，剧本里有你必须公开的信息（方便游戏推进），也有你必须保守的秘密，在游戏的最后会进行投票（找出谁是凶手）。游戏的结算方式是积分制，一旦你的秘密泄露就会被扣分；相反，如果你发现了别人的秘密可以加分。
另外，剧本看完要回收，也就是说游戏过程中不能看剧本！
（没错...这就是凶手的剧本！图片来源：城西生活圈））
过程中会有一个类似法官的角色，这个游戏里被称为“导演”。比如像最开始的介绍剧情，游戏过程中时不时扔几个彩蛋，以及最后投票的唱票都是由导演来完成的。
（图片来源：城西生活圈）
游戏开始之后，我们除了可以通过聊天来交换信息和套“秘密”，还可以通过10枚游戏代币来获得额外的线索——花1枚可以获得一个案发现场的线索，花2枚可以获得一个在场人物的线索。
不过，连续的两个线索必须是不同类型的，也就是说如果你第一次调查的是案发现场，那么第二次就必须调查人物，以此类推。
（图片来源：城西生活圈）
到底谁才是凶手呢？
就不告诉你！
棋士桌游推理馆还有很多不同主题的房间，每个房间至少都可以搭配两个不同的剧本。像小编体验的就是福尔摩斯主题房间，这里还可以被用来演绎《漫画家离奇死亡事件》的剧本。
福尔摩斯主题房间
（图片来源：棋士桌游推理馆）
《漫画家离奇死亡事件》剧情梗概：月刊杂志《漫画GO》三年来一直连载着一部火热的漫画，为其作者带来了金钱和地位。就当事业如日中天，却曝出了惊人的噩耗，这位天才作者死在了自己公寓的卧室里！一连串的真相慢慢被揭开。。。难度：☆☆☆☆；适宜5-6人
宫廷斗争主题房间
（图片来源：棋士桌游推理馆）
相匹配的剧本有《朱颜血泪》和《隋唐大运河》：
（图片来源：棋士桌游推理馆）
《朱颜血泪》剧情梗概：咸丰年间，政局混乱。清王朝与浩罕国之间冲突不断，为了缓和两国的矛盾，浩罕国答应与大清和亲。美若天仙的浩罕国公主嫁到了清王朝，被封为昭妃，很快就独占了皇帝的恩宠。不曾想，昭妃身体虚弱，日渐消瘦，皇帝命令最有名的太医为她治病。但是一碗汤药喝下去后，昭妃却当场香消玉殒。皇帝下命令彻查此事，浩罕国送亲的将军也赶来讨要说法。皇子，大臣，大内总管，曾经的宠妃等人齐聚一堂，灯火辉煌的殿堂照亮不了心底的阴暗，勾心斗角无非为了那一丝最原始的欲望。这场宫内宫外的博弈，到底有几人能笑到最后？难度：☆☆☆☆☆；适宜8人
《隋唐大运河》剧情梗概：公元605年，隋炀帝下令开凿大运河，欲贯通南北，连通经济，加强控制。带动了沿线无数小城镇的发展，安越乡也因此热闹了起来。分属朝廷两大派系的商行锦绣和兴隆行均派了管事来争夺运河开凿权，而此时运河经过土地的所有权发生了纠纷，本地蛮夷也因为神庙被牵扯到了里面。更糟糕的是土地主竟发生了意外，事情变得错综复杂。道士、蛮夷、官差、商阀、农夫、郎中......被各自的目的所卷在了一起，为名？为利？还是为了所珍惜的人？一时间爱恨情仇、国耻家怨迸发而出。难度：☆☆☆☆☆；适宜10人
医院主题房间
（图片来源：棋士桌游推理馆）
医院主题房间有《纯白的恶意》和《白衣死神》两个剧本。
（图片来源：棋士桌游推理馆）
《纯白的恶意》剧情梗概：昭和三十五年（1960年）的秋天福岛县福岛市圣尤丽安娜医院，年初时因为一场意外的车祸，导致65岁的南部哲也老人高位截瘫，至今为止他已经在这里呆了大半年了。老人的两个儿子和一个儿媳妇经常来医院探望老人，医院的工作人员对老人的照顾也可以说是无微不至，尽心尽力。可是今天，老人的大儿子再度来到病房探望老人的时候，却惊恐地发现，南部哲也老人静静地躺在病床上，已经停止了呼吸。。。。。。难度：☆☆☆☆；适宜7、8人
《白衣死神》剧情梗概：这个医院的急诊病房是最好的急诊病房之一，那里有全国有名的专业的医护人员。医生们见过太多的死亡，但今晚的死亡非同寻常，它笼罩在谋杀的阴影下突然来袭！同时这所医院流传着诸多的传说，今晚你能找出各个真相吗？难度：☆☆☆☆☆☆；适宜8、9人
（图片来源：棋士桌游推理馆）
因为全民大侦探的游戏时间都比较长，一般速度差不多要3小时左右，建议大家去之前可以先预约好剧本，另外场次也是固定的，每天有三场，分别是：12：00-15：00、15：30-18：30、19：00-22：00
（图片来源：棋士桌游推理馆）
如果去早了，还可以先和小伙伴们玩玩桌游！“棋士桌游”可不是白叫的，一整个架子的游戏任你挑！
（图片来源：城西生活圈）
一起去破案！
城西生活圈将免费送上1组免费名额（不限场次、不限人数），以及10组半价名额（限6人主题房间）。
后台回复关键词“棋士”报名
【棋士桌游推理馆】
预定电话：微信：mmcs2270
游戏地址：西城店：文二路古墩路颐景园综合楼1001庆春店（主题店）：庆春路中河中路交叉口金峰大厦901（顾家家居楼上）
人均：平时99元/人，周末139/人
*文中图片来源：城西生活圈、棋士桌游推理馆
责任编辑：
声明：本文由入驻搜狐号的作者撰写，除搜狐官方账号外，观点仅代表作者本人，不代表搜狐立场。
今日搜狐热点