题解：AT_abc456_f [ABC456F] Plan Holidays

好像很简单，为什么我不会。

首先考虑怎么 DP，记 $dp_{i,0}$ 表示第 $i$ 个位置不是节假日，$dp_{i,1}$ 表示是节假日。

那我们的转移也很容易：

$$dp_{i,0} = dp_{i - 1, 1}$$

（如果连着两个都不是节假日，那么这两天就不可能通过在两个节假日之间变成节假日，不符合题意）

$$dp_{i, 1} = \min(dp_{i - 1, 0}, dp_{i - 1, 1}) + A_i$$

初始化就是区间往前一个位置的值了，按照定义就是 $dp_{l - 1, 0} = 0$ 和 $dp_{l - 1, 1} = A_{l - 1}$。由于 $A_{0}$ 根本不存在，所以我们直接把它设置成 $\infty$，可以避免在不存在的位置放节假日。

我赛时做到这里的时候就不知道该怎么搞了，实际上这个转移可以转化为 $\min$ 和 $+$ 运算的矩阵乘法。转移式子相当于：

$$dp_{i,0} = \min(dp_{i - 1, 0} + \infty, dp_{i - 1, 1} + 0)$$

$$dp_{i, 1} = \min(dp_{i - 1, 0} + A_i, dp_{i - 1, 1} + A_i)$$

于是我们得到：

$$\begin{pmatrix} dp_{i, 0} \\ dp_{i, 1} \end{pmatrix} = \begin{pmatrix} \infty & 0 \\ A_i & A_i \\ \end{pmatrix} \begin{pmatrix} dp_{i - 1, 0} \\ dp_{i - 1, 1} \end{pmatrix}$$

这里就相当于用开头的 DP 数组不断乘上中间一堆矩阵得到的结果，所以用线段树维护即可，时间复杂度 $O(n \log n)$。

注意按照上面的转移，线段树里合并顺序应该是从右到左。

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node {
    vector<vector<int>> m;
    node(int n) : m() {
        m.assign(n, vector<int>(n, 0));
    };
    node(vector<vector<int>> _m) : m(_m) {};
    node operator*(node b) {
        vector<vector<int>> res(m.size(), vector<int>(b.m[0].size(), 1e18));
        for (int i = 0; i < m.size(); i++) {
            for (int k = 0; k < m[0].size(); k++) {
                for (int j = 0; j < b.m[k].size(); j++) {
                    res[i][j] = min(res[i][j], m[i][k] + b.m[k][j]);
                }
            }
        }
        return node(res);
    }
};
struct tag
{
    tag() {}
    void apply(tag t) {
    }
};
struct dat
{
    node val;
    int len;
    dat() : val({}) {}
    dat(node _val) : val(_val) {}
    friend dat operator + (dat x, dat y) {
        dat tp;
        tp.val = y.val * x.val;
        tp.len = x.len + y.len;
        return tp;
    }
    void apply(tag t) {
    }
};
template<class dat, class tag>
struct LazySegtree
{
    int n;
    vector<dat> bit1;
    vector<tag> bit2;
    void init(int n, dat k = dat()) {
        init(vector<dat>(n + 1, k));
    }
    void init(vector<dat> v) {
        n = v.size() - 1;
        bit1.assign((n << 2) + 3, dat());
        bit2.assign((n << 2) + 3, tag());
        function<void(int, int, int)> build = [&](int x, int l, int r) {
            if (l == r) {
                bit1[x] = v[l];
                bit2[x] = tag();
                return;
            }
            int mid = (l + r) / 2;
            build(x << 1, l, mid);
            build(x << 1 | 1, mid + 1, r);
            pushup(x);
        };
        build(1, 1, n);
    }
    LazySegtree() : n(0) {}
    LazySegtree(int n, dat k = dat()) {
        init(n, k);
    }
    template<class T>
    LazySegtree(vector<T> v) {
        init(v);
    }
    void pushup(int x) {
        bit1[x] = bit1[x << 1] + bit1[x << 1 | 1];
    }
    void apply(int x, tag t) {
        bit1[x].apply(t);
        bit2[x].apply(t);
    }
    void pushdown(int x) {
        apply(x << 1, bit2[x]);
        apply(x << 1 | 1, bit2[x]);
        bit2[x] = tag();
    }
    void update(int x, int l, int r, int L, int R, tag t) {
        if (l <= L && R <= r) {
            apply(x, t);
            return;
        }
        pushdown(x);
        int mid = (L + R) / 2;
        if (l <= mid) {
            update(x << 1, l, r, L, mid, t);
        }
        if (r > mid) {
            update(x << 1 | 1, l, r, mid + 1, R, t);
        }
        pushup(x);
    }
    void update(int l, int r, tag t) {
        if (l > r) return;
        update(1, l, r, 1, n, t);
    }
    void update(int x, int pos, int L, int R, dat t) {
        if (L == R) {
            bit1[x] = bit1[x] + t;
            return;
        }
        pushdown(x);
        int mid = (L + R) / 2;
        if (pos <= mid) {
            update(x << 1, pos, L, mid, t);
        } else {
            update(x << 1 | 1, pos, mid + 1, R, t);
        }
        pushup(x);
    }
    void update(int pos, dat t) {
        update(1, pos, 1, n, t);
    }
    dat query(int x, int l, int r, int L, int R) {
        if (l <= L && R <= r) {
            return bit1[x];
        }
        int mid = (L + R) / 2;
        dat tp;
        bool flag = 0;
        if (l <= mid) {
            tp = query(x << 1, l, r, L, mid);
            flag = 1;
        }
        if (r > mid) {
            tp = (flag ? tp + query(x << 1 | 1, l, r, mid + 1, R) : query(x << 1 | 1, l, r, mid + 1, R));
        }
        return tp;
    }
    dat query(int l, int r) {
        if (l > r) return dat();
        return query(1, l, r, 1, n);
    }
};
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    vector<dat> init(n + 1, dat(node({})));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        init[i] = dat(node({{(int)1e18, 0}, {a[i], a[i]}}));
    }
    a[0] = 1e18;
    LazySegtree<dat, tag> seg(init);
    int ans = LLONG_MAX;
    for (int i = 1; i + k - 1 <= n; i++) {
        auto tp = seg.query(i, i + k - 1);
        ans = min(ans, min(tp.val.m[1][0], tp.val.m[1][1] + a[i - 1]));
    }
    cout << ans << '\n';
}
signed main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}