web analytics

uva1354 天平难题 解题报告

uva1354 天平难题。主要有 回溯法,二叉树模拟。

当然,这道题也有很多剪枝,但是这个用二叉树性质模拟的数组应该过了,这样写,这道题,完全就足够了。

原题目链接:https://uva.onlinejudge.org/external/13/1354.pdf

题目大意:

就是首先给你一个房间的宽度r,之后有s个挂坠,第i个挂坠的重量是wi,设计一个尽量宽,但是不能宽过房间.的天平。当然会有好几组这样的数据。

这些天平棍的长度都为1,天平棍要么挂 挂坠,要么就继续挂木棍设挂的木棍必须要让天平平衡,满足n*a==m*b。这就是个物理概念。

其它东西,题目里写的很清楚。

而这道题整体思想就是 1,枚举二叉树。2,计算宽度。

 

枚举二叉树,很显然用到的是dfs+回溯。

二叉树的模型,主要就用的是这个东西来枚举 like根==i子节点== i*2,i*2+1,这样的。

从第二个点开始枚举。其中dfs(num,sit,use)

num:代表这个节点编号,

sit:现在这棵树中有多少位置可供填写。

use:现在有use个挂件还可以用。

PS:枚举的时候还要注意,每次进到一个新点的时候要判断父亲节点是不是天平棍,-1为棍,如果不是棍,就++,找下一个节点。

 

计算宽度的时候,从最后一个点开始往前递推。设以这个节点为0,左边就是负长度,而右边就是正长度。这就很好的解释了其中

l[i]=min(-L+l[x],R+l[y]);

r[i]=max(-L+r[x],R+r[y]);

这段代码的意思。

 

Post a Comment

You must be logged in to post a comment.