某工厂的流水线上有 T 个工位，产品依次经过每个工位进行加工。为了降低能耗，工厂决定关闭其中 k 个工位，让产品直接跳过这些工位。工程师发现，当某个工位被关闭时，产品会因为缺少该环节的加工而产生一定的质量偏差。
具体来说，用一个长度为 T-1 的偏差值列表来描述关闭每个工位的影响：列表中第 t 个元素（0<=t<T-1，从0开始编号）表示关闭第 t+1 号工位后，产品所增加的质量偏差值。
但是，连续两个相邻工位不能同时关闭，否则产品的结构完整性无法保证。请你设计一个方案，在满足约束的前提下恰好关闭 k 个工位，使得总质量偏差最小。如果无法找到满足条件的关闭方案，则输出 -1。
[编程题]关闭工位
- 热度指数：37 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行一个正整数 T，表示流水线上的工位总数（1<T<=1000）。
第二行一个非负整数 k，表示需要关闭的工位数（0<=k<T）。
第三行 T-1 个正整数，以空格分隔，表示关闭对应工位后所增加的质量偏差值，每个值均为小于 1000 的正整数。
输出描述:
输出一个整数。如果存在合法的关闭方案，输出最小的总质量偏差值；否则输出 -1。
示例1
输入
5 2 3 1 4 2
输出
3
说明
共 5 个工位，需要关闭 2 个，偏差列表为 [3, 1, 4, 2]。最优方案是关闭第 2 号和第 4 号工位（对应偏差值 1 和 2），总偏差为 1+2=3。注意不能同时关闭第 1 号和第 2 号（相邻），也不能同时关闭第 3 号和第 4 号（相邻）。
示例2
输入
4 3 5 8 3
输出
-1
说明
共 4 个工位，偏差列表长度为 3，最多只能关闭 2 个不相邻的工位（例如第 1 号和第 3 号），无法关闭 3 个不相邻的工位，因此输出 -1。
备注:
本题由牛友@Charles 整理上传
题目链接
关闭工位
题目描述
某工厂流水线上有 个工位。为了降低能耗，工厂决定恰好关闭其中 个工位。
关闭第 个工位（）会产生偏差值 。
限制条件：连续两个相邻工位不能同时关闭。
请你设计一个方案，在满足约束的前提下恰好关闭 个工位，使得总质量偏差最小。如果无法找到满足条件的关闭方案，则输出
展开全文
问题信息
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
