#1863. 人间应又雪

    ID: 1863 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1823来源:qoj.ac数据:公开样例贪心

人间应又雪

人间应又雪

题目描述

标题: 人间应又雪 - Problem - QOJ.ac

#9563. 人间应又雪

Statistics

The problem was used in the following contests:

长度为 n 的街道被积雪覆盖,将街道划分为 n 段,第 i 段的积雪量为 ai,保证 0≤ai≤m 且 ai 为整数。

天依与言和要来清理积雪,每次清理有 2 种选择:

  • 天依从位置 1 走到位置 x,将积雪清理掉 c,再走回位置 1。同时,因为在雪地上移动,位置 1∼x 的积雪量减少 1,即 ∀i∈[1,x−1],ai:=ai−1,ax:=ax−c−1。
  • 言和从位置 n 走到位置 x,将积雪清理掉 c,再走回位置 n。同时,因为在雪地上移动,位置 x∼n 的积雪量减少 1,即 ∀i∈[x+1,n],ai:=ai−1,ax:=ax−c−1。

任意时刻,积雪量对 0 取 max。

天依与言和想知道,最少进行多少次清理后(即最小化两人清理次数总和),能将所有积雪清除,即 ∀i∈[1,n],ai=0。

输入格式

本题有多组测试数据。

首先输入一行两个数 T,tid,T 表示数据组数,tid 表示子任务编号(样例的子任务编号为 0)。

对于每组数据:

第一行三个整数 n,m,c。

第二行 n 个整数 a1∼an。

输出格式

对于每组数据,输出一行一个整数表示答案。

测试样例

样例输入 1

1 0
5 5 1
1 3 2 3 1

样例输出 1

2

样例解释 1

天依走到位置 4 清理,积雪量变为 [0,2,1,1,1]。

言和走到位置 2 清理,积雪量变为 [0,0,0,0,0]。

共 2 次清理。

样例 2

见附加文件中的 snow.in 与 snow.ans。这个样例中有 100 组 n=10,m=10 的数据。

数据范围

对于 100% 的数据,1≤T≤105,1≤n,m≤5×105,∑n,∑m≤106,0≤ai≤m,0≤c≤5×105。

子任务编号 n m 特殊限制 分值 子任务依赖 1 ≤5×105 ≤5×105 c=0 2 2 ≤2 无 3 3 ≤5 ≤5 T≤105 4 4 ≤50 ≤50 ∑n,∑m≤200 10 3 5 ≤300 ≤300 ∑n,∑m≤600 10 4 6 ≤2000 ≤2000 ∑n,∑m≤4000 10 5 7 ≤5×104 ≤5×104 c≤20,∑n,∑m≤105 20 8 ∑n,∑m≤105 15 6, 7 9 ≤5×105 ≤5×105 c≤20 10 1, 7 10 无 15 2, 8, 9

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1 0
5 5 1
1 3 2 3 1
2