「JSOI2014」打兔子

「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
#include
#include
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
template void chkmax(T &a, const T& b) { a = a > b ? a : b; }
template inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (&＃39;0&＃39; > c || c > &＃39;9&＃39;) f |= c == &＃39;-&＃39;, c = getchar();
while (&＃39;0&＃39; <= c && c <= &＃39;9&＃39;) 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 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;
}