#P18795. [Omi2022] 蛇梯与传送门
[Omi2022] 蛇梯与传送门
[Omi2022] 蛇梯与传送门
题目描述
有一条从左到右的数轴,一枚棋子从所有传送门端点的左边出发,不断向右移动,直到走到所有端点的右边。
数轴上已经放置了 对双向传送门。第 对的两个端点位于 ,所有端点的位置互不相同。
当棋子从左向右到达某个传送门端点时,它立即传送到配对的另一个端点,然后从那个位置继续向右移动。刚刚通过传送到达的端点不会立即再次触发传送,棋子会继续寻找严格在当前位置右侧的下一个端点。
同一对传送门可以在后续行程中再次触发。每触发一次传送,得分增加 。
你可以再增加至多 对双向传送门。新端点可以放在任意实数位置,但不能与任何其他端点重合。特别地,可以在任意两个已有端点之间、所有端点左边或所有端点右边放置新端点。
请计算最优放置后能够获得的最大得分。只需要输出最大得分,不需要输出放置方案。
输入格式
第一行包含两个整数 。
接下来 行,每行包含两个整数 ,表示一对已有传送门的两个端点。
输出格式
输出一个整数,表示增加至多 对传送门后能够获得的最大得分。
样例输入
3 1
5 6
1 4
2 3
样例输出
6
样例说明
可以在 和 放置一对新传送门,最终触发传送的次数为 。
数据范围与分组
- ;
- ;
- ,所有 个端点的位置互不相同。
| 分值 | 额外限制 |
|---|---|
| 10 | |
| 15 | 对所有传送门均有 |
| 19 | |
| 31 | 无额外限制 |