题解 | 关闭工位

import sys

def solve():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    T = int(next(it))
    K = int(next(it))
    loss = []
    for i in range(T - 1):
        loss.append(int(next(it)))

    INF = 10 ** 18
    # 定义最优状态数组，dp0代表前一个工位没关闭，dp1代表前一个工位关闭（后一个因为相邻不能关闭）
    # 例如，dp0[i]代表已经关闭了i个工位，且该情况中最后一个工位（如：总共5个工位12345，当后面循环遍历到4号工位时，“最后一个”代表3号工位）没关闭的情况
    dp0 = [INF] * (K + 1)
    dp1 = [INF] * (K + 1)

    # 两种极端情况
    if K == 0:
        print(0)
        return
    if K > T // 2:
        print(-1)
        return
    
    # 逐个遍历工位质量偏差
    for i in range(T - 1):
        if i == 0:
            dp0[0] = 0
            dp1[1] = loss[0]
            continue
        # 根据当前遍历工位的质量偏差，逐个遍历最优情况列表并更新
        for j in range(K, 0, -1):
            # dp0[j]由两种情况产生
            # 1.上个工位没关闭
            a = dp0[j]
            # 2.上个工位关闭
            b = dp1[j]
            dp0[j] = min(a, b)
            dp1[j] = min(dp1[j], dp0[j - 1] + loss[i])

    ans = min(dp0[K], dp1[K])
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    solve()