Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
可怜见,20多次用RE来试探题意,终于过了。最短路线的起点要根据示例来猜测尝试,明确一下模糊的题意1。 每个时间点记录的可见数据是完整的,也就是说这个位置/时间点观测到的目标一定出现在指定位置上,而没有观测到的目标一定不在观察者可以看到的两条街道上 2。 每个目标只在一条街道上匀速来回在两点间移动,时间到后停止移动 3。 注意,观察记录里有些数据里,可能目标已经停止移动了 4。 我是使用最后一个位置作为最短路线的起点的,计算在所有目标都静止不动后的最短路线 算法其实很水,对每个观察目标,暴力搜索其起点/终点,不冲突则记下终点的位置,最后枚举贪心计算最短路线的长度,复杂度x*y*p Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator