当前位置：首页 > news >正文

F - Plan Holidays

news 2026/5/3 23:45:16

F - Plan Holidays

Problem Statement

Takahashi is trying to decide his schedule for $N$ days. Initially, none of the days are holidays.

He can repeat either of the following operations any number of times:

Choose an integer $i$ between $1$ and $N$, inclusive, and make day $i$ a holiday. This operation costs $A_i$.
Choose an integer $i$ between $2$ and $N-1$, inclusive, such that both day $i-1$ and day $i+1$ are already holidays, and make day $i$ a holiday. This operation is free.

Find the minimum total cost required to create a consecutive block of $K$ or more holidays.

$T$ test cases are given; solve each of them.

Constraints

$1 \leq T \leq 2 \times 10^5$
$1 \leq K \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$
All input values are integers.
The sum of $N$ over all test cases is at most $2\times 10^5$.

Input

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Here, $\mathrm{case}_i$ denotes the input for the $i$-th test case. Each test case is given in the following format:

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

Sample Input 1

3
5 2
3 1 4 1 5
6 4
24 3 22 39 4 29
15 7
220651272 302798780 874479994 657822311 613294668 479624013 241168404 610547619 762548286 256160531 823041612 951553052 226556081 649525901 153805947

Sample Output 1

2
29
1902064780

For the first test case, a consecutive block of at least two holidays can be created by performing operations as follows:

Make day $2$ a holiday using the first type of operation. This costs $1$.
Make day $4$ a holiday using the first type of operation. This costs $1$.
Make day $3$ a holiday using the second type of operation. This is free.

The total cost of this sequence of operations is $2$. It is impossible to create a consecutive block of two or more holidays with a cost less than $2$, so output $2$.

解题思路

本题要求在 $n$ 天中安排假期（初始均无假期），有两种操作：花费 $a_i$ 的代价将第 $i$ 天设为假期；当第 $i-1$ 天和第 $i+1$ 天均是假期时，可免费将第 $i$ 天设为假期。目标是求出获得至少 $k$ 个连续假期所需的最小总代价。

首先，最优解中被选为假期的位置一定恰好构成一段连续区间。这是因为若存在多段不相邻的连续假期区间，我们总可以通过取消多余区间来回收成本，而不会使解变差；若两段区间仅间隔一个位置，则可以免费填充该间隔位置进行合并，也不会使最优解变差。因此，最优解一定只包含一段连续区间。

进一步地，这段连续区间的长度在最优解中只可能是 $k$ 或 $k+1$。如果区间长度至少为 $k+2$，我们总可以从区间某一端点开始撤销选择以回收成本（若端点内侧存在依赖于该端点才满足免费条件的假期，需一并撤销）。重复此过程，直到区间长度小于 $k+2$。由于每次取消操作会移除 $1$ 个或 $2$ 个位置，最终区间长度必然回落至 $k$ 或 $k+1$。

于是，问题简化为枚举所有长度为 $k$ 和 $k+1$ 的连续区间，分别求解选择该区间的最小成本，再取全局最小值。对于固定区间 $[l, r]$，可以用 dp 求解。定义 $f(i)$ 表示选择 $[l, i]$ 区间且第 $i$ 个位置通过消耗代价选择的最小成本。根据第 $i-1$ 个位置是否消耗代价进行转移，状态转移方程为 $$f(i) = \min\{f(i-1), f(i-2)\} + a_i$$

最终选择区间 $[l, r]$ 的最小成本即为 $f(r)$。然而，如果对每个枚举的子区间独立求解，时间复杂度为 $O(nk)$。

针对这类需要对某段区间进行动态规划的问题，一般都需要将转移方程转化为矩阵乘法的形式，并利用线段树维护求解。由于上述转移仅涉及加法与取最小值运算，我们可以将其转化为 min-plus 代数（又称 $(\min, +)$ 半环）下的矩阵乘积，即用加法代替普通矩阵乘法中的乘法，用取最小值代替加法，具体推导可以参考 min 与 + 运算转换成类似于矩阵乘法的推导过程。根据状态依赖关系，可以构造矩阵 $A_i = \begin{bmatrix} +\infty & a_i \\ 0 & a_i \end{bmatrix}$，使得 $\begin{bmatrix} f(i-2) & f(i-1) \end{bmatrix} \otimes A_i = \begin{bmatrix} f(i-1) & f(i) \end{bmatrix}$。通过递推，区间 $[l, r]$ 的结果可表示为 $$\begin{bmatrix} f(r-1) & f(r) \end{bmatrix} = \begin{bmatrix} f(l-1) & f(l) \end{bmatrix} \otimes \bigotimes\limits_{i=l+1}^{r} A_i$$

其中 $f(l-1)$ 是初始状态，当枚举长度为 $k$ 的区间时规定 $f(l-1)=0$，而枚举长度为 $k+1$ 的区间时规定 $f(l-1)=+\infty$。为了统一处理，我们可以将初始状态均设为 $f(l-1)=a_{l-1}$（规定 $a_0=+\infty$）。这相当于将区间隐式向左扩展一个位置，使总长度变为 $k+1$。因此，只需枚举所有长度为 $k$ 的区间即可同时涵盖长度 $k$ 和 $k+1$ 的全部情形。

具体实现时，用线段树维护所有位置的 min-plus 代数下的矩阵乘积，随后枚举所有长度为 $k$ 的连续区间 $[l, r]$，通过计算初始状态向量 $\begin{bmatrix} a_{l-1} & a_l \end{bmatrix}$ 与区间矩阵连乘的乘积，即可快速得到 $f(r)$ 作为该区间的最小成本。

AC 代码如下，时间复杂度为 $O(n\log{k})$：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 2e5 + 5;
const LL INF = 0x3f3f3f3f3f3f3f3f;int a[N];
struct Matrix {array<array<LL, 2>, 2> a;Matrix(array<array<LL, 2>, 2> b = {}) {a = b;}auto& operator[](int x) {return a[x];}Matrix operator*(Matrix b) {Matrix c;for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {c[i][j] = INF;for (int k = 0; k < 2; k++) {c[i][j] = min(c[i][j], a[i][k] + b[k][j]);}}}return c;}
};
struct Node {int l, r;Matrix f;
}tr[N * 4];void build(int u, int l, int r) {tr[u] = {l, r};if (l == r) {tr[u].f = Matrix({INF, a[l], 0, a[l]});}else {int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);tr[u].f = tr[u << 1].f * tr[u << 1 | 1].f;}
}Matrix query(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) return tr[u].f;int mid = tr[u].l + tr[u].r >> 1;if (r <= mid) return query(u << 1, l, r);if (l >= mid + 1) return query(u << 1 | 1, l, r);return query(u << 1, l, r) * query(u << 1 | 1, l, r);
}void solve() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];}build(1, 1, n);LL ret = INF;a[0] = INF;for (int i = 1; i + m - 1 <= n; i++) {if (m == 1) ret = min<LL>(ret, a[i]);else ret = min(ret, (Matrix({a[i - 1], a[i]}) * query(1, i + 1, i + m - 1))[0][1]);}cout << ret << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}