P7987

清小秋ovo · 2022-01-01 00:34:43 · 题解

USACO GOLD 2021 DEC T1

原题链接: usaco 官网

洛谷链接: p7987

题意

题意还是比较清晰的，n 头牛在一个数轴上，每头牛一个重量 y_i 和位置 x_i 。只要位置差不超过 k 的两头奶牛可以进行配对，对于每头奶牛而讲，要么属于一组，要么不属于任何一组。

求出未配对奶牛的最大重量和最小重量的和。

解题思路

我们来分类讨论一下这道题：

最小体重

对于 T=1 的情况，首先考虑贪心。

我们可以先将所有的牛进行分组，即如果存在两头相邻的牛且它们之间的距离超过 K 则我们把下一头牛放在另外一组当中。这样一来就保证了在每个组当中 没有两头相邻奶牛的距离是超过 K 的 在这样的情况下，所有的偶数头牛的组都可以被正好配完。

重点就在于奇数头奶牛的组应当如何处理。

为了最小化答案，我们肯定只想丢掉一头牛。所以只要确保以下两个条件中的任意一个成立就可以考虑抛弃该头奶牛：

1. 该奶牛在当前组内抛弃后左边的奶牛和右边的奶牛数量均为偶数。
2. 该奶牛的前一头奶牛和后一头奶牛的差小于 K。

关于第一个条件，原因显然，因为只有这要断链才能够保证剩下的子链都为偶数个牛构成，按照我们之前的对于“一组牛”的定义是必然能够完全分配的。(如下图所示)

这样的话，相当于我们直接考虑所有下标为奇数的牛（如果是从0开始的话则是所有下标为偶数的牛）

关于第二个条件，当分出去的奶牛不一定能够保证产生两条偶数子链时，如果这头牛前面的牛和后面的牛的距离差在 K 的范围内，那么我们就也可以把这两头牛配对起来，同样的也能够使得剩下的两组牛数量为偶数，必然能完全分配。(如下图所示)

所以只需要枚举所有可以丢掉的牛的最小值即可。

时间复杂度: \mathcal{O}(N)

最大体重

(比赛的时候想了半天转移式也没想出来，最后等比赛结束后看了 Andy Qu的题解才整明白的)

对于 T=2 的情况，首先考虑动归。

那么动归老套路：

1. 定义数组：设 dp[i][j] 为考虑第 i 头牛至当前组的最后一头牛，存在 j 个未配对的奶牛时所能取到的最大值。
2. 对于每头牛来讲，要么配对，要么不配对。如果配对的话，则需要计算剩下的不配对牛的最大数量和。
3. 当第 i 个牛不被配对的情况下，设 ub[i] 为处在第 i 个牛右边最左端的可以不被配对的牛的坐标

那么这样我们就可以推出转移方程:

当第 i 头牛可以不不被配对时则有了下面的一式，而当第 i 头牛无法被不配对时则有二式

可以通过二分来计算 ub[i] 。

维护二维数组的时间复杂度为: \mathcal{O}(N \log N) 注意：遍历时需要从后往前进行计算

代码

代码这里就不放了，可以参考官方给出的题解代码

参考资料

官方原题解