hodf 快乐题

· · 题解

（前置：这篇题解中不区分“菜地”“菜田”“点”等名词，偏意识流，建议感性理解。）

首先我们考虑 2k\ge n 的情况。

当 n=3，此时 k 只能是 2 或者 3，我们发现兔子怎么跑没啥区别，所以就找到最大的 k 个 r_i 求和即可。

当 n\gt3，我们直接依次在所有标号为奇数的菜地上全都来一枪，兔子一定全打完了，剩下的枪随便乱打就好了，答案是 \sum_{i=1}^n r_i。这里要用到这么一个性质，按这个打法，打完一个点之后其与其两边再也不会有兔子，（兔子不能直接在一个点的左右邻点横跳，而 n=3 违背了这一点，故须单独考虑。）而这在这里是显然的。

（不过实际上 n=k=3 可以合并到这里来，只要特判一下 n=3,k=2 的时候要把加出来的总和减掉最小的一个 r_i。）

那么接下来我们来考虑 2k\lt n，这个时候我们最好就是把 k 枪打全了。（其实不打全也有可能，之所以和上面分开，后面会解释。）不难想到特判 k=0 然后剩下的情况直接动态规划。我们现在考虑在最优策略下（假设 k 枪打满的情况下）证明这么两件事情：

  1. 一片菜地只会被打一枪。

  2. 不存在相邻的两片菜地都被打枪了。

首先，在 n=3 的时候，我们迄今为止还没特判过的只有一种情况：k=1。这是显然成立的。

否则的话，欲证明之，我们试图去证明之前我们分析 2k\ge n\gt3 的时候提到的那个结论：存在一个最优策略下使得打完一个点之后其与其两边再也不会有兔子。打完一个点之后，如果它两边不再有兔子，那么显然中间也不再会有兔子（因为不会有兔子被吓过来）。然后这个问题的结构是对称的，于是我们现在只要证明：打完 r_1 之后，r_2 不会再有兔子。

我们考虑反之，r_2 的兔子是哪里来的？如果是从 r_1 来的，那 r_1 的兔子只能是从 r_n 来的。这个时候我们对 r_n 展开证明即可。换而言之，我们这里其实是不妨设 r_2 比 r_n 先出现兔子，那 r_2 的兔子就只能是从 r_3 被吓过来的。这只能是一种情况：r_4 被打了一枪，然后 r_3 的兔子被吓到了 r_2，此后 r_3 又被打了一枪，然后 r_3 的兔子又到了 r_2……不过这个时候 r_3 哪来的兔子？因为如果是空枪，与我们枪枪不空的假设矛盾。这说明 r_4 在 r_1 之前就违背了我们上面欲证的性质，我们只需要不妨假设 r_1 是最优策略下最先违背性质的点，便可导出矛盾。

（以上是作者的证明心路，可能比较意识流，但看得懂就行=.=）

然后有了这两条，我们就可以设计 DP 了：

设 dp_{i,j,k} 表示：打 i 枪，打前 k 个点，第 k 个点打没打（j=0 就是没打，j=1 就是打了）。这里我们强制第一个点不能打。

这个东西的转移非常显然，如果没打，那就枚举上一个点打没打；如果打了，就枚举上一枪在不在 k-2。（如果在就拿过来转移，如果不一定在就直接用 k-1 没打来转移。）为什么要这么分呢？因为如果在 k-2 的话要多考虑一个 r_{k-1} 被吓了过来……

但这会有一个问题：第 n 个点和第 1 个点的状态会互相干扰。不过这其实很好处理。就，分两类，第一个点没打（直接用上面的那个 DP 即可），和第一个点打了。第二种情况的话直接强制第一个点打掉，那么第 n 个点的 r_n 只兔子会被吓走（稍微处理一下就好了），这个时候由结论我们可以得知一定不会打第二块菜田了，于是可以把菜田们平移一下（实现是传指针，因为这里相当于把第二块菜田搞成了那个一定不能打的第一块菜田），然后再 DP。

代码很好写。但有个细节：不合法状态要设成 -\infty（可以用 memset 0xc0 实现），而不是 0。另外我们可以发现这个写法是可以对 i 跑滚动数组省掉一维，于是空间复杂度降为线性（时间还是平方）。

代码参考：

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 4009;
int dp[2][2][N];
int DP(int* r, int n, int k) {
  memset(dp, 0xc0, sizeof dp);
  memset(dp[0][0], 0, sizeof dp[0][0]);
  for (int i = 1; i <= k; ++i)
    for (int j = 2; j <= n; ++j)
      dp[i & 1][0][j] = max(dp[i & 1][0][j - 1], dp[i & 1][1][j - 1]),
             dp[i & 1][1][j] =
                 max(dp[~i & 1][0][j - 1], dp[~i & 1][1][j - 2] + r[j - 1]) +
                 r[j];
  return max(dp[k & 1][0][n], dp[k & 1][1][n]);
}
int n, k, r[N];
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> r[i];
  int ans;
  if (!k)
    ans = 0;
  else if ((k << 1) >= n)
    ans = accumulate(r + 1, r + n + 1,
                     n == 3 && k == 2 ? -*min_element(r + 1, r + n + 1) : 0);
  else
    ans = DP(r, n, k), r[n - 1] += r[n],
    ans = max(ans, DP(r + 1, n - 2, k - 1) + r[1]);
  return cout << ans << endl, 0;
}

以上。