关闭工位

题目分析

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

思路

经典不相邻选取 DP

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

个物品中，最多能选 个不相邻的。若 ，直接返回 。

设 为从前 个物品中选 个不相邻物品的最小偏差和：

$$

• 不选第 个：继承
• 选第 个：第 个不能选，从 转移

初始条件：，，。

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

以样例验证：，，。选物品 2 和 4（不相邻），偏差 。

复杂度

• 时间复杂度：
• 空间复杂度：，滚动数组优化后

代码

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()

复杂度

• 时间复杂度：
• 空间复杂度：