luogu#P4985. 反射
反射
题目背景
最近玩了一个十分好玩的游戏,通过摆放能量发射器,来攻击敌人的飞船。
但是十分手残以及脑残,总是玩不过十分简单的关卡,所以他想请你帮助他。
题目描述
这个游戏是这样的,你有个能量发射器启动器,可以启动任何个在一个初始平台上发射器,然后发射器会向北偏东方向上发射能量光束,能量值为。在有场地里面有块悬浮的平台,这些平台上有的装有两种能量发射器发射器和发射器的其中一种,功能如下:
-
对于发射器,如果它装在平台上方,它会向北偏东方向上发射能量光束,能量值为;如果装在下方,它会向南偏东方向上发射能量光束,能量值为。
-
对于发射器,不管装在什么地方它会同时向北偏东和南偏东发射能量光束,能量值为。
但是,悬浮平台上的发射器并不会自己启动,必须在有能量光束击中它所在的平台上时才会启动,且这个发射器发射的能量为给定的值(注意一束光击中这些平台,只有在这个能量光束的来的路径上没有该击中平台提供的能量时这些平台的发射器就会启动,每被击中一次就发射一次,如下图,1号发射给2号2号激活,其中一个击回1号,此时1号不会再发射一次(也就是能量不会再次叠加))
你在最开始只能启动初始平台上的能量发射器中的个(这个是依次启动的,且每个只能发射一次,但是其它地方的发射器可以发射多次)。
将地图抽象为二维平面直角坐标系,其中的直线为地面(光束到达地面会消失,但是如果地面有平台则优先击中平台),那么所有的平台包括初始平台均平行于轴,敌人的飞船可以看做为一个平行于轴的,两个端点为和,当一条光束击中飞船它便会受到光束来的这条路径上的所有能量值的和的伤害然后光束就会消失。(光束击中其它平台并不会反弹,而是会被平台吸收作为能量来启动发射器)。
请你求出在启动哪些开始的发射器,使得让飞船受到的伤害最大,请你求出这个最大值。
输入格式
第一行两个正整数,表示你能启动个开始的发射器,总共有个平台。 第二行四个整数,表示初始平台位置,初始平台上每一个整点有一个发射器能发射初始能量为的能量光束(如时,有三个初始位置的发射器)。 第三行三个整数,表示敌人飞船位置。 下面行,每行描述了一个平台,格式如下:
- 表示一个空的平台
- 表示在的位置一个发射器在的平台上,发射能量为,最后的或表示在平台的上方还是下方,为上方,为下方。
- 表示在的位置一个发射器在的平台上,发射能量为。
输出格式
一行一个整数表示最大的伤害值。
1 3
1 2 1 5
8 1 7
1 4 5 3 5 5 0
2 4 5 5 5 5
1 5 6 6 6 5 1
25
1 11
0 2 1 10
17 3 11
0 1 2 6
1 3 5 5 4 30 0
1 4 7 4 6 10 1
2 4 8 7 6 14
1 7 10 2 9 10 0
1 8 11 10 9 14 1
1 11 13 7 12 10 0
2 11 13 5 12 14
1 11 13 1 12 10 0
2 13 14 8 14 6
1 13 15 3 14 10 0
242
提示
样例解释:
样例如图:
最优为橙色那个,绿色的为。
样例如图:
只有橙色那条打出来为,其他两条只有。
数据范围:
-
对于的数据;
-
对于的数据所有平台(不包括飞船)的长度和不超过;
-
对于的数据;
-
对于的数据;
-
对于的数据,坐标的,坐标,所有的能量值的值均在内,且保证每个发射器必定在一个平台上,且平台长度与敌人飞船的长度大于等于。保证最开始的平台长度不超过,且所有的平台不会重叠;
-
还有的额外数据同,只是;
输入较大,建议使用较快的读入方式。