题解与讨论区 1162: 集结

题解与讨论区 1162: 集结

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MB  Special Judge

返回问题页面

题目描述

张老师一直希望同济大学能够进入ICPC的World Final,但是觉得同济大学ACM队太弱了。他想召集世界各地的上古大神来带领同济ACM队进行训练。
假设世界是一个1*n的一维地图,所有格子的坐标都是1到n之间的整数。一开始地图上某一些格子有一位上古大神,其他的格子会有一些事件。每个格子里面只有一位上古大神或者只有一个事件。张老师希望能请到上古大神能集中到一个格子上。
约定集结的坐标点之后,上古大神们依次开始移动。每一次有一位上古大神向着集结的坐标直线前进,不会向相反方向走。当一位上古大神进入一个格子的时候,如果这个格子里面有一个事件没有触发,那么就会触发这个事件让上古大神获得或者失去一些体力。当上古大神某一个时刻体力小于0的时候就不能到达集结点了(等于0依然可以到达)。一个事件只会触发一遍,已经触发过之后就不会再触发了。一位上古大神移动结束之后,另一位上古大神才开始移动。
张老师希望能将上古大神都请过来,但是不知道怎么安排集结点和移动顺序才能让所有人都能到达。他想让你规划一个集结的方案。
注意所有上古大神都需要移动且仅移动一次,即使是和集结点在一个坐标上也需要移动。

第1162题的题解