题意
给定一个长度为 $n$ 的序列 $a$，请对 $k$ 从 $1$ 到 $\lceil \dfrac n2 \rceil$，回答出使 $k$ 个数严格大于他两边的数，至少需要进行多少次让其中一个数加一或减一的操作数量。
$n = 5000$
题解
非常明显是 DP。
状态设计
$f(i, j, 0)$ 表示 前 $i$ 个数，有 $j$ 个满足要求的，其中 $i - 1$ 和 $i$ 都不满足要求 的最小花费。
$f(i, j, 1)$ 表示 前 $i$ 个数，有 $j$ 个满足要求的，$i - 1$ 不满足要求，其中 $i$ 满足要求 的最小花费。
$f(i, j, 2)$ 表示 前 $i$ 个数，有 $j$ 个满足要求的，$i - 1$ 满足要求，其中 $i$ 不满足要求 的最小花费。
转移方程
$f(i, j, 0) = \min\{f(i - 1, j, 0), f(i - 1, j, 2)\}$
$f(i, j, 1) = \min\{f(i - 1, j - 1, 0) + [\;a(i - 1) \geq a(i)\;]\ a(i - 1) - a(i) + 1,\newline\qquad\qquad\qquad\quad f(i - 1, j - 1, 2) + [\;\min\{a(i - 10), a(i - 2) - 1\} \geq a(i)\;]\ \min\{a(i - 1), a(i - 2) - 1\} - a(i) + 1\}$
- 从 $f(i - 1, j - 1, 0)$ 转移过来：此状态的 $i - 2$ 是不满足要求的，所以第 $i - 1$ 座山的高度没有被下降过。
- 从 $f(i - 1, j - 1, 2)$ 转移过来：此状态的 $i - 2$ 是满足要求的，所以第 $i - 1$ 座山的高度被下降到了 $\min\{a(i - 1), a(i - 2) - 1\}$
$f(i, j, 2) = f(i - 1, j, 1) + [\;a(i) \geq a(i - 1)\;]\ a(i) - a(i - 1) + 1$
可以滚动数组，把 $i$ 那一维滚掉
代码
#include <algorithm> // By rbtree (https://rbtree.archi)
#include <array> // Please submit with C++14!
#include <bitset>
#include <cmath>
#include <complex>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#define ddo //
#endif
#define ra (scanf("%lld", &__TEMP_READ_VALUE), __TEMP_READ_VALUE)
typedef long long tp;
tp __TEMP_READ_VALUE;
using namespace std;
////////////////////////////////////////////////////////////////////////////////
constexpr tp Hat_N = 5003;
signed main() {
tp n = ra;
array<tp, Hat_N> a;
array<array<tp, 3>, Hat_N / 2> f;
for (auto&& i : f) {
i.fill(-1ull >> 2);
}
f[0][0] = f[1][1] = 0;
for (tp i = 1; i <= n; ++i) {
a[i] = ra;
}
for (tp i = 2; i <= n; ++i) {
for (tp j = i + 1 >> 1; j; --j) {
f[j][0] = min(f[j][0], f[j][2]);
f[j][2] = f[j][1] + max(0ll, a[i] - a[i - 1] + 1);
f[j][1] =
min(f[j - 1][0] + max(0ll, a[i - 1] - a[i] + 1),
f[j - 1][2] + max(0ll, min(a[i - 1], a[i - 2] - 1) - a[i] + 1));
}
}
for (tp i = 1; i <= n + 1 >> 1; ++i) {
printf("%lld ", min(f[i][0], min(f[i][1], f[i][2])));
}
return 0;
}