题目内容
（请给出正确答案）
[主观题]
问题描述:机器人Rob可在一个树状路径上自由移动.给定树状路径T上的起点s和终点t,机器人要从s运
动到t.树状路径T.上有若干可移动的障碍物.由于路径狭窄,任何时刻在路径的任何位置不能同时容纳2个物体.每步可以将障碍物或机器人移到相邻的空顶点上.设计一个有效算法用最少移动次数使机器人从s运动到t.
算法设计:对于给定的树T,以及障碍物在树T中的分布情况,计算机器人从起点s到终点t的最少移动次数.
数据输入:由文件input.txt提供输入数据.文件的第1行有3个正整数n,s和t,分别表示树T的顶点数,起点s的编号和终点t的编号.
接下来的n行分别对应于树T中编号为0,1,...,n-1的项点.每行的第1个整数h表示顶点的初始状态,当h+1时表示该顶点为空顶点,当h=0时表示该顶点为满顶点,其中已有一个障碍物.第2个数k表示有k个顶点与该项点相连.接下来的k个数是与该顶点相连的顶点编号.
结果输出:将计算出的机器人最少移动次数输出到文件output.txt.如果无法将机器人从起点s移动到终点t,则输出“NoSolution!"
答案
查看答案
上的乘法表如表3-1所示.对任一定义于Σ上的字符串,适当加括号后,得到,个表达式.例如,对于字符串x=bbba,它的一个加括号表达式为(b(bb)(ba).依乘法表,该表达式的值为a试设计一个动态规划算法,对任一定义于Σ上的字符串 计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a.
,计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a.
.有向直线L上的每个点x都有权值w(xi),每条有向边
都有一个非负边长
.有向直线L上的每个点x可以看作客户,其服务需求量为w(xi)e每条边
的边长
.在点x0处已设置了服务机构,现在要在直线L上增设2处服务机构,使得整体服务转移费用最小.
接下来的n行中,每行有2个整数.第i+1行的2个整数分别表示
和
.
的残冠
.每个作业Ji都有2项任务分别在2台机器上完成.每个作业必须先由机器1处理,再由机器2处理.作业Ji需要机器j的处理时间为tij(=1,2,...,n;j=1,2).对于一个确定的作业调度,设Fij是作业i在机器j上完成处理的时间.所有作业在机器2上完成处理的时间和
称为该作业调度的完成时间和.
