题意
给定一个长度为 $n$ 的环，环上第 $i$ 个点有权值 $U_i$。选择其中 $k$ 个点，对于一段连续的选择的点，除第一个点外其余计入答案。求最大的答案。
$1 \leq b < n \leq 3830$
题解
我们在 $\left(n, 1\right)$ 间断开环，变成一条链，然后 DP，$f\left(i, j, 0/1\right)$ 表示现在在第 $i$ 个点，已经选择了 $j$ 个点，第 $i$ 个点是否被选择。
转移方程：
$$f\left(i, j, 0\right) = \max\{f\left(i - 1, j, 0\right), f\left(i - 1, j, 1\right)\}$$
$$f\left(i, j, 1\right) = \max\{f\left(i - 1, j - 1, 1\right) + U_i, f\left(i - 1, j - 1, 0\right)\}$$
强制选 $n$ 时，初始值 $f\left(1, 0, 0\right) = 0, f\left(1, 1, 1\right) = U_1$，答案是 $f\left(n, b, 1\right)$
强制不选 $n$ 时，初始值 $f\left(1, 0, 0\right) = f\left(1, 1, 1\right) = 0$，答案是 $f\left(n, b, 0\right)$
时间复杂度 $\mathcal O(n \cdot b)$
代码
// Please submit with C++14!
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define ra _Read()
using tp = int;
tp _Read();
using namespace std;
constexpr bool __MTCS__ = 0;
constexpr tp Hat_N = 3833;
namespace __SOL__ {
tp n, b;
array<tp, Hat_N> u;
pair<tp, tp> dp(tp f111) {
array<array<array<tp, 2>, Hat_N>, Hat_N> f;
for (auto&& i : f) {
for (auto&& [j, k] : i) {
j = k = -(-1u >> 2);
}
}
f[1][0][0] = 0;
f[1][1][1] = f111;
for (tp i = 2; i <= n; ++i) {
f[i][0][0] = f[i - 1][0][0];
for (tp j = 1; j <= b; ++j) {
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1]);
f[i][j][1] = max(f[i - 1][j - 1][1] + u[i], f[i - 1][j - 1][0]);
}
}
return make_pair(f[n][b][0], f[n][b][1]);
}
signed main() {
pair<tp, tp> temp;
n = ra;
b = ra;
for (tp i = 1; i <= n; ++i) {
u[i] = ra;
}
temp = dp(0);
printf("%d\n", max({temp.first, temp.second, dp(u[1]).second}));
return 0;
}
} // namespace __SOL__
signed main() {
tp __MTCS__ = ::__MTCS__ ? ra : 1;
while (__MTCS__--) {
__SOL__::main();
}
return EXIT_SUCCESS;
}
tp _Read() {
bool __neg(0);
char __c(getchar());
tp __val(0);
for (; __c < 48 || __c > 57; __c = getchar()) {
__neg = __c == 45;
}
for (; __c > 47 && __c < 58; __c = getchar()) {
__val = __val * 10 + (__c & 15);
}
return __neg ? ~__val + 1 : __val;
}
/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/