SP12409 LCPC12H - Johnny at school

Johnny 在学校度过了漫长的一天后，决定和朋友们玩一个叫做“点游戏”的小游戏。游戏规则如下：在一条水平线上有 $N$ 个点依次排列，每个点 $i$ 有一个半径为 $R[i]$。玩家可以从任意一个点开始移动，但只能移动到后续的点，并且该点的半径必须比前一个点的大。当他在点 $i$ 上停留时，会获得 $P[i]$ 分。要想赢得游戏，Johnny 需要经过最多数量的点；如果有多种路径可以通过相同数量的点，则他应该选择获得分数最高的路径；如果仍有多种选择，他应该选取字典序最大的路径（对于序列 $A=(a_1, a_2, \dots, a_n)$ 和 $B=(b_1, b_2, \dots, b_n)$ 若第一个不相等的元素满足 $a_x > b_x$，则 $A$ 的字典序大于 $B$）。Johnny 是个聪明的孩子，他想要达到最佳结果，所以他请求你的帮助，看看最优的路径应该如何走。你能帮他赢得游戏吗？

首先输入一个整数 $T$ 表示测试用例的数量。每个测试用例第一行是一个整数 $N$（表示点的数量）。接下来有 $N$ 行，每行包含两个整数 $R[i]$ 和 $P[i]$，分别表示第 $i$ 个点的半径和停留在该点可获得的分数。

对于每个测试用例，输出应以结果序号 $K$（从 1 开始）开头，后跟句号和一个空格，然后按访问顺序打印 Johnny 走过的点的索引（基于 1 的索引）。相同数量点、相同分数时，输出字典序最大的子序列。

- $1 \le T \le 10$ - $1 \le N \le 1500$ - 每个点的半径 $1 \le R[i] \le 300$ - 停留在每个点可获得的积分 $1 \le P[i] \le 2,000,000$ ### 示例 #### 输入 ``` 2 6 1 3 2 3 6 3 4 20 3 15 9 10 6 1 3 1 3 6 3 4 20 3 15 9 10 ``` #### 输出 ``` 1. 1 2 4 6 2. 2 4 6 ``` 这个例子中，我们可以看到在第一组输入数据中，通过点 1、2、4 和 6 是最优策略，而在第二组数据中，选择点 2、4 和 6 会是最佳选择。 **本翻译由 AI 自动生成**