首先有结论：一个位置上的数要么不变，要么操作成 \(\infty\)，要么操作成 \(0\)。
证明
对于 \(a_i\)，考察其相邻两个数形成的值域区间 \([\min(a_{i-1},a_{i+1}),\max(a_{i-1},a_{i+1})]\)，分类讨论操作后 \(a_i\) 的取值：
- \(a_i\in [\min(a_{i-1},a_{i+1}),\max(a_{i-1},a_{i+1})]\)：这种时候不如不操作。
- \(a_i<\min(a_{i-1},a_{i+1})\)：直接令 \(a_i\gets 0\) 显然不劣。
- \(a_i>\max(a_{i-1},a_{i+1})\)：直接令 \(a_i\gets \infty\) 显然不劣。
结论得证。\(\Box\)
那么可以列出 DP：用 \(f_{i,0/1,0/1/2,L_1,L_2}\) 表示考虑了前 \(i\) 个数，当前是上升/下降段，\(a_i\) 不操作/操作成了 \(0\)/操作成了 \(\infty\)，当前上升/下降段的长度为 \(L_1\)，以 \(a_i\) 结尾的值相同的极长段的长度为 \(L_2\)，此时的前缀最小操作次数。转移时简单考虑 \(a_{i+1}\) 和 \(a_i\) 的大小关系即可，记录 \(L_2\) 是因为单调性变化时需要把 \(L_2\) 继承过去。DP 过程中需要保证 \(L_1<k\)。这样就有了 \(\mathcal{O}(n^3)\) 的做法。
这里需要指出，我们构造的序列一定可以进行调整，使得不存在 \(0/\infty\) 构成的长度 \(>1\) 的连续段。具体来说吗，对于每个这样的连续段，我们从末尾开始依次调整为 \(0,1,0,1,\cdots\) 即可，\(\infty\) 是类似的。后续的证明和构造都需要用到这个调整。
考虑比较神仙的优化，固定 \(i,0/1,0/1/2\)，考察状态 \((v,L_1,L_2)\)，其中 \(v\) 是 DP 值，那么 DP 状态之间是有偏序关系的：
-
若 \(v\) 不同，则 \(v\) 更小的状态一定更优。
设 \(v\) 更小的状态为 \(S_1\)，更大的为 \(S_2\)。我们从 \(i\) 开始一直扩展到 \(n\)，这样得到了一个操作序列 \(Q\)，若 \(S_2\) 执行了 \(Q\) 中操作后仍然合法，则考察 \(S_1\)：若 \(S_1\) 操作后也是合法的，则显然 \(v\) 较小的更优；否则我们可以进行调整，把 \(S_1\) 第一次不合法的位置的前一位根据单调性修改成 \(0/+\infty\)，这样就可以令 \(L_1,L_2\) 清空，显然比 \(S_2\) 更优。
-
若 \(v\) 相同，\(L_1\) 不同，则 \(L_1\) 更小的状态一定更优。
题解大多是这么写的，但认真思考就能发现问题：在单调性不改变时，这么做貌似没有问题；但是如果单调性改变，则 \(L_1\) 会把原状态的 \(L_2\) 继承过来，此时反而是 \(L_2\) 小的更优。怎么回事呢？
我们指出：对于状态集合中任意两个状态 \(S_1,S_2\)，必然存在其中一个状态，它的 \(L_1,L_2\) 都不劣于令一个状态。
证明
反证。考虑两个状态 \(S_1,S_2\)，其中 \(S_1\) 的 \(L_1\) 比 \(S_2\) 的大，\(S_1\) 的 \(L_2\) 比 \(S_2\) 的小。那么 \(S_1\) 的 \(L_2\) 部分必然没有修改，于是 \(S_2\) 多出来的那部分 \(L_2\) 就是全部修改成 \(0/\infty\)，矛盾。\(\Box\)
-
若 \(v,L_1\) 相同，则 \(L_2\) 更小的状态一定更优。
正确性显然。
因此对于固定的 \(i,0/1,0/1/2\)，我们只需要按照上述比较方式，存下来最优的 \((v,L_1,L_2)\) 即可。这样对于每个 \(i\) 只需要存 \(6\) 个三元组。进一步地，可以发现其中两个状态是无用的，也就是说我们只需要存 \(4\) 个三元组。
构造方案直接记录前驱还原即可。时间复杂度为 \(\mathcal{O}(n)\)。
主要代码
int n, m, a[N], b[N];
pii S[4] = {{0, 0}, {0, 2}, {1, 0}, {1, 1}};struct DP {int val, len1, len2;friend bool operator<(const DP &lhs, const DP &rhs) {if (lhs.val != rhs.val) return lhs.val < rhs.val;else if (lhs.len1 != rhs.len1) return lhs.len1 < rhs.len1;else return lhs.len2 < rhs.len2;}
} f[N][4], dp_inf;
int g[N][4];int id(pii st) {for (int i = 0; i < 4; ++i) if (st == S[i]) return i;return -1;
}int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> a[i];dp_inf = {inf, 0, 0};for (int i = 0; i <= n; ++i) fill(f[i], f[i] + 4, dp_inf);f[0][0] = {0, 0, 0}, a[0] = -inf;for (int i = 0; i < n; ++i) for (int j = 0; j < 4; ++j) {auto [dir, ch] = S[j];auto [val, len1, len2] = f[i][j];if (val == inf) continue;int prv = !ch ? a[i] : (ch == 1 ? -inf : inf);for (int k = 0; k < 3; ++k) {int ndir;if (k == 1) ndir = 1;else if (k == 2) ndir = 0;else ndir = a[i + 1] == prv ? -1 : a[i + 1] < prv;auto upd = [&](pii st, const DP &v) {int num = id(st);if (~num && v.len1 < m && v < f[i + 1][num])f[i + 1][num] = v, g[i + 1][num] = j;};int nval = val + (k > 0);if (ndir == -1) upd({dir, k}, {nval, len1 + 1, len2 + 1});else if (dir == ndir) upd({ndir, k}, {nval, len1 + 1, 1});else upd({ndir, k}, {nval, len2 + 1, 1});}}int cur = min_element(f[n], f[n] + 4) - f[n];cout << f[n][cur].val << '\n';bool flag = 0;int prv_ch = 0;for (int i = n; i; --i) {auto [_, ch] = S[cur];if (ch > 0 && ch != prv_ch) flag = 0;prv_ch = ch; b[i] = !ch ? a[i] : (ch == 1 ? flag : V - flag);if (ch > 0) flag ^= 1;cur = g[i][cur];}for (int i = 1; i <= n; ++i) cout << b[i] << ' ';return 0;
}