标签：

「JSOI2014」打兔子

传送门

首先要特判 \(k \ge \lceil \frac{n}{2} \rceil\) 的情况，因为此时显然可以覆灭所有的兔子，也就是再环上隔一个点打一枪。

但是我们又会发明当 \(n = 3, k = 2\) 时，这种情况也满足上述条件但是我们只能打失两群兔子，，所以选兔子最多的两个格子打。

对付剩下的情况我们可以考虑 \(\text{DP}\) 。

我们可以发明一件事，就是说如果我们把环弱化成链，那么顺着打就可以包罗所有状态了。

所以说我们就可以有一本性质：两个相邻的格子不会被同时打。

然后我们就在链上先跑 \(\text{DP}\) ：设 \(dp_{i, j, 0 / 1}\) 暗示在前 \(i\) 个格子中开了 \(j\) 枪，第 \(i\) 个格子有没有开枪的最大收益。

转移就是：

第 \(i+1\) 个格子不开 ： \(dp_{i + 1, j, 0} \leftarrow \max\{dp_{i, j, 0}, dp_{i, j, 1}\}\)

第 \(i\) 个格子不开，第 \(i + 1\)个格子开：\(dp_{i + 1, j + 1, 1} \leftarrow dp_{i, j, 0} + a_{i + 1}\)

第 \(i\) 个格子开，第 \(i + 1\) 个格子不开，第 \(i + 2\) 个格子开：\(dp_{i + 2, j + 1, 1} \leftarrow dp_{i, j, 0} + a_{i + 1} + a_{i + 2}\)

然后对付环的问题，我们就讨论一下第 \(1\) 个格子和第 \(n\) 个格子的开枪情况即可。

参考代码：

#include <algorithm> #include <cstring> #include <cstdio> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) using namespace std; template < class T > void chkmax(T &a, const T& b) { a = a > b ? a : b; } template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } const int _ = 4010; int n, k, a[_], dp[_][_][2]; inline void DP() { for (rg int i = 1; i < n; ++i) for (rg int j = 0; j <= k; ++j) { chkmax(dp[i + 1][j][0], max(dp[i][j][0], dp[i][j][1])); if (j + 1 <= k) chkmax(dp[i + 1][j + 1][1], dp[i][j][0] + a[i + 1]); if (j + 1 <= k && i + 2 <= n) chkmax(dp[i + 2][j + 1][1], dp[i][j][1] + a[i + 1] + a[i + 2]); } } inline int calc1() { memset(dp, 0xaf, sizeof dp), dp[1][0][0] = 0; DP(); return dp[n][k][0]; } inline int calc2() { int tmp = a[n]; a[n - 1] += tmp, a[n] = 0; memset(dp, 0xaf, sizeof dp), dp[1][1][1] = a[1], DP(); a[n] = tmp, a[n - 1] -= tmp; return dp[n][k][0]; } int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n), read(k); for (rg int i = 1; i <= n; ++i) read(a[i]); int ans = 0; if (k >= (n + 1) / 2) { if (n == 3 && k == 2) sort(a + 1, a + n + 1), printf("%d\n", a[2] + a[3]); else { for (rg int i = 1; i <= n; ++i) ans += a[i]; printf("%d\n", ans); } return 0; } chkmax(ans, calc1()); chkmax(ans, calc2()); reverse(a + 1, a + n + 1); chkmax(ans, calc2()); printf("%d\n", ans); return 0; }

「JSOI2014」打兔子