Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届省赛真题-最优清零方案
题目 2689:

蓝桥杯2022年第十三届省赛真题-最优清零方案

时间限制: 3s 内存限制: 576MB 提交: 1307 解决: 153

题目描述

给定一个长度为 N 的数列 A1, A2, · · · , AN。现在小蓝想通过若干次操作将这个数列中每个数字清零。

每次操作小蓝可以选择以下两种之一:

1. 选择一个大于 0 的整数,将它减去 1;

2. 选择连续 K 个大于 0 的整数,将它们各减去 1。

小蓝最少经过几次操作可以将整个数列清零?

输入格式

输入第一行包含两个整数 N 和 K。

第二行包含 N 个整数 A1, A2, · · · , AN

输出格式

输出一个整数表示答案。

样例输入

4 2
1 2 3 4

样例输出

6

提示

对于 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。 

标签