小码农

趣味编程-面向每个人的创意编程

最优清零方案

avatar 2022-12-07 15:57 774次浏览 0 条评论 C++

题目描述

给定一个长度为N的数列A1, A2, … , AN。
现在小蓝想通过若干次操作将这个数列中每个数字清零。
每次操作小蓝可以选择以下两种之一:
1. 选择一个大于0的整数,将它减去1;
2. 选择连续K个大于0的整数,将它们各减去1。
小蓝最少经过几次操作可以将整个数列清零?

输入格式

输入第一行包含两个整数N和K。
第二行包含N个整数A1, A2, … , AN。
对于20% 的评测用例,1 ≤ K ≤ N ≤ 10。
对于40% 的评测用例,1 ≤ K ≤ N ≤ 100。
对于50% 的评测用例,1 ≤ K ≤ N ≤ 1000。
对于60% 的评测用例,1 ≤ K ≤ N ≤ 10000。
对于70% 的评测用例,1 ≤ K ≤ N ≤ 100000。
对于所有评测用例,1 ≤ K ≤ N ≤ 1000000, 0 ≤ Ai ≤ 1000000。

输出格式

输出一个整数表示答案。

输入样例

4 2
1 2 3 4

输出样例

6
发表评论