A6165. 「USACO 2021.12 Platinum」Paired Up
编程题
省选/NOI-
知识点
题目描述
数轴上总计有 $N$（$1≤N≤5000$）头奶牛，每一头奶牛都是荷斯坦牛（Holstein）或更赛牛（Guernsey）之一。第 $i$ 头奶牛的品种为 $b_i∈\{H,G\}$，第 $i$ 头奶牛的位置为 $x_i$（$0≤x_i≤10^9$），而第 $i$ 头奶牛的重量为 $y_i$（$1≤y_i≤10^5$）。
根据 Farmer John 的信号，某些奶牛会组成对，使得
- 每一对包含位置相差不超过 $K$ 的一头荷斯坦牛 $h$ 和一头更赛牛 $g$（$1≤K≤10^9$）；也就是说，$|x_h−x_g|≤K$。
- 每一头奶牛要么包含在恰好一对中，要么不属于任何一对。
- 配对是极大的；也就是说，没有两头未配对的奶牛可以组成对。
你需要求出未配对的奶牛的重量之和的可能的范围。具体地说，
- 如果 $T=1$，计算未配对的奶牛的最小重量和。
- 如果 $T=2$，计算未配对的奶牛的最大重量和。
根据 Farmer John 的信号，某些奶牛会组成对，使得
- 每一对包含位置相差不超过 $K$ 的一头荷斯坦牛 $h$ 和一头更赛牛 $g$（$1≤K≤10^9$）；也就是说，$|x_h−x_g|≤K$。
- 每一头奶牛要么包含在恰好一对中，要么不属于任何一对。
- 配对是极大的；也就是说，没有两头未配对的奶牛可以组成对。
你需要求出未配对的奶牛的重量之和的可能的范围。具体地说，
- 如果 $T=1$，计算未配对的奶牛的最小重量和。
- 如果 $T=2$，计算未配对的奶牛的最大重量和。
输入格式
输入的第一行包含 $T$，$N$ 和 $K$。
以下 $N$ 行，第 $i$ 行包含 $b_i,x_i,y_i$。输入保证 $0≤x_1<x_2<⋯<x_N≤10^9$。
以下 $N$ 行，第 $i$ 行包含 $b_i,x_i,y_i$。输入保证 $0≤x_1<x_2<⋯<x_N≤10^9$。
输出格式
输出未配对的奶牛的最小或最大重量和。
输入输出样例
输入 #1
2 5 4 G 1 1 H 3 4 G 4 2 H 6 6 H 8 9
输出 #1
16
输入 #2
1 5 4 G 1 1 H 3 4 G 4 2 H 6 6 H 8 9
输出 #2
6
输入 #3
2 10 76 H 1 18 H 18 465 H 25 278 H 30 291 H 36 202 G 45 96 G 60 375 G 93 941 G 96 870 G 98 540
输出 #3
1893
说明/提示
- 测试点 4-7 满足 $T=1$。
- 测试点 8-14 满足 $T=2$ 且 $N≤300$。
- 测试点 15-22 满足 $T=2$。
- 测试点 8-14 满足 $T=2$ 且 $N≤300$。
- 测试点 15-22 满足 $T=2$。