关闭工位

题目分析

工厂有 $T$ 个工位，需要关闭恰好 $k$ 个工位以节能。给定 $T-1$ 个偏差值，分别对应工位 $1$ 到 $T-1$ 的质量偏差。要求不能同时关闭相邻的两个工位，在满足约束的前提下最小化总偏差。若无合法方案则输出 $-1$ 。

思路

经典不相邻选取 DP

从 $T-1$ 个物品中选 $k$ 个不相邻的，使权值之和最小。这是经典问题。

$n = T-1$ 个物品中，最多能选 $\lceil n/2 \rceil$ 个不相邻的。若 $k > \lceil n/2 \rceil$ ，直接返回 $-1$ 。

设 $dp[i][j]$ 为从前 $i$ 个物品中选 $j$ 个不相邻物品的最小偏差和：

$ $dp[i][j] = \min(dp[i-1][j],\ dp[i-2][j-1] + \text{dev}[i])$ $

不选第 $i$ 个：继承 $dp[i-1][j]$
选第 $i$ 个：第 $i-1$ 个不能选，从 $dp[i-2][j-1]$ 转移

初始条件： $dp[0][0] = 0$ ， $dp[1][0] = 0$ ， $dp[1][1] = \text{dev}[1]$ 。

用滚动数组优化空间，只保留前两行。

以样例验证： $T=5$ ， $k=2$ ， $\text{dev}=[3,1,4,2]$ 。选物品 2 和 4（不相邻），偏差 $1+2=3$ 。

复杂度

时间复杂度： $O(T \cdot k)$
空间复杂度： $O(k)$ ，滚动数组优化后

代码

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    T = int(input_data[idx]); idx += 1
    k = int(input_data[idx]); idx += 1
    n = T - 1
    dev = []
    for i in range(n):
        dev.append(int(input_data[idx])); idx += 1

    if k == 0:
        print(0)
        return

    max_sel = (n + 1) // 2
    if k > max_sel:
        print(-1)
        return

    INF = float('inf')
    prev2 = [INF] * (k + 1)
    prev1 = [INF] * (k + 1)
    prev2[0] = 0
    prev1[0] = 0
    prev1[1] = dev[0]

    for i in range(2, n + 1):
        curr = [INF] * (k + 1)
        for j in range(k + 1):
            curr[j] = prev1[j]  # 不选第 i 个
            if j > 0 and prev2[j - 1] < INF:
                curr[j] = min(curr[j], prev2[j - 1] + dev[i - 1])  # 选第 i 个
        prev2 = prev1
        prev1 = curr

    print(prev1[k])

main()

复杂度

时间复杂度： $O(T \cdot k)$
空间复杂度： $O(k)$