涉及知识点：动态规划

题目链接

题意

给你一个数轴，数轴上有\(n\)个点，选其中一些点进行两两配对，配对要求是这两个点之间距离不能超过\(k\)，且一个点只能有一组配对，使得未配对的点之间无法再进行配对。每个点有个代价\(y_i\)，我们称一种配对方案的代价为未配对的点的代价和，求配对方案的最大或最小代价

分析

求最值，数据范围只能过\(O(n\log n)\)以下，很有可能是动态规划，我们分成两种情况讨论

T=1，求最小

由于代价的来源是未选择的点，所以我们在处理的时候应该反过来思考，我们不是去选点来配对，而是给一些点打上标记，让剩下没有标记的点都能配对，而我们要保证的事就是标记点之间距离必须大于\(k\)，而为了使剩下的点都能配对，显然相邻的两点配对最优

我们将状态设为 \(f[i][j]\) 表示处理完前\(i\)头奶牛，其中标记了 \(j\) 头牛（未配对），剩下 \((i-j)\) 头牛没有被标记（两两配对）。那么我们就可以进行如下分类讨论：

• 如果\((i-j)\)为偶数，说明前面未标记的牛都已经配对了

  • 给第\(i\)个点打上标记，这样做没有任何限制
  • 不打标记，那么这个点和下一个点匹配，这样做需要保证 \(i\) 到 \(i+1\) 距离小于等于\(k\)

• 如果\((i-j)\)为奇数，由于我们是相邻点之间进行配对，此时说明最后一个点（即第\(i-1\)个点）还找不到对象（雾）

  • 给第\(i\)个点打上标记，那么上一个点和下一个点匹配，这样做需要保证 \(i-1\) 到 \(i+1\) 的距离小于等于\(k\)
  • 不打标记，那么这个点和上一个点匹配，这样做需要保证 \(i-1\) 到 \(i\) 的距离小于等于\(k\)，但在讨论 \(i-1\) 时已经保证了此条件，不用再判断

  思维误区：有人会问如果第\(i-1\)的点被打了标记怎么办，但是此时\((i-j)\)为偶数。可以证明\((i-j)\)为奇数时第\(i-1\)个点不可能被打上标记

但是，这样空间复杂度是\(O(n^2)\)的，过不去\(10^5\)的数据，怎么改进？

注意到一点，得知\((i-j)\)的奇偶性不一定需要知道 \(j\) 具体的数值，只需要记录 \(i\) 和 \(j\) 的奇偶性，当 \(i\) 与 \(j\) 奇偶性相反时，\((i-j)\)为奇数，反之为偶数

那么我们引出一个新的变量 \(j'\)，当 \(i\) 为奇数时 \(j'\) 为 \(1\)，\(i\) 为偶数时 \(j'\) 为 \(0\) 。那么 \(f[i][j']\) 意味着 \(i\) 和\(j\) 奇偶性相同，表示\((i-j)\)为偶数的情况；\(f[i][!j']\) 意味着 \(i\) 和 \(j\) 奇偶性相反，表示\((i-j)\)为奇数的情况。这样 \(f\) 数组就只用开 \(10^5\times 2\) 的大小了

我们重新思考具体的状态转移怎么写：

（我们令 \(last\) 表示【到 \(i\) 距离大于 \(k\) 的最大的点】）

• \((i-j)\)为偶数时
  • 给该点打标记，那么就要从 \(j-1\) 的状态转移而来（与当前 \(j\) 奇偶相反），f[i][j']=min(f[i][j'],f[last][!j']+y[i])
  • 不打标记