Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

可怜见,20多次用RE来试探题意,终于过了。最短路线的起点要根据示例来猜测尝试,明确一下模糊的题意

Posted by lddlinan at 2020-10-24 19:59:21 on Problem 1531
1。 每个时间点记录的可见数据是完整的,也就是说这个位置/时间点观测到的目标一定出现在指定位置上,而没有观测到的目标一定不在观察者可以看到的两条街道上
2。 每个目标只在一条街道上匀速来回在两点间移动,时间到后停止移动
3。 注意,观察记录里有些数据里,可能目标已经停止移动了
4。 我是使用最后一个位置作为最短路线的起点的,计算在所有目标都静止不动后的最短路线

算法其实很水,对每个观察目标,暴力搜索其起点/终点,不冲突则记下终点的位置,最后枚举贪心计算最短路线的长度,复杂度x*y*p

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator