#CW63. 宝石劫案(jewels)
宝石劫案(jewels)
题目描述
平面上有 颗位置互不相同的宝石,每颗宝石属于 种颜色中的一种。第 颗宝石的位置为 ,颜色为 ,其中颜色编号为 到 ,并且每种颜色至少出现一次。
机械手只能抓取一次。它选择一条水平线段:设线段所在高度为 ,左右端点的横坐标为 和 ,其中 。机械手会抓走所有同时满足 且 的宝石;在线段上、线段正下方以及更低位置的宝石都会被抓走,端点上的宝石也包含在内。
一次抓取是安全的,当且仅当被抓走的宝石所包含的颜色集合不是全部 种颜色,也就是至少有一种颜色的宝石完全没有被抓走。请在所有可能的 中,求一次安全抓取最多能得到的宝石数量。
输入格式
从 jewels.in 文件中读入。
第一行是测试组数 。每组数据先给出宝石数量 和颜色种数 ,随后给出 行。第 行包含 ,分别表示第 颗宝石的横坐标、纵坐标和颜色编号。输入保证每种颜色至少有一颗宝石。
输出格式
从 jewels.out 文件中输出。
按测试组的输入顺序输出答案,每组一行一个整数,表示满足安全条件时一次抓取最多能得到的宝石数。
样例 1 输入
1
10 3
1 2 3
2 1 1
2 4 2
3 5 3
4 4 2
5 1 2
6 3 1
6 7 1
7 2 3
9 4 2
样例 1 输出
5
样例 1 解释
取 、、,被抓走的宝石为 、、、、,共 颗,只包含颜色 ,缺少颜色 ,因此这次抓取是安全的。可以证明不存在能安全抓走 颗或更多宝石的方案。
数据范围
对全部数据,。每组数据满足 ,,,,且每种颜色至少出现一次。另有总量限制 。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 25 | ||
| 2 | |||
| 3 | |||
| 4 | 完整数据范围 |