Comet OJ

C0452 [CTSC2009Day1-C]序列变换

内存限制：256 MB 时间限制：3000 ms

题目描述

给定一个整数序列 $X_1,X_2,X_3,...,X_n$ ​和三个正整数 $Q,A,B$满足：

  • $1≤X_i≤Q$ 对于任意 $1≤i≤n$；
  • $X_i≤X_{i+1}$ 对于任意 $1≤i<n$；
  • $A≤\frac{Q−1}{n−1}$ 且 $A≤B$。

对于任意 $1≤i≤n$，做如下变换：$Y_i=X_i+\Delta_i$，其中 $\Delta_i$ 是一个整数。使得新序列 $Y$ 满足如下性质：

  • $1≤Y_i≤Q$ 对于任意 $1≤i≤n$；
  • $Y_{i+1}−Y_i∈[A,B]$ 对于任意 $1≤i<n$。

对于这样一个变换，所需代价定义为

$TransformCost(X,Y)=\sum_{i=1}^n∣\Delta_i∣$

本题的任务即为寻找一个变换，使得 $TransformCost(X,Y)$ 最小化。

输入格式

第一行 4 个整数，$N,Q,A,B$。接下来一行包含 $N$ 个整数，分别为 $X_1,X_2,X_3,...,X_n$。

输出

仅包含一行，为最小的 $TransformCost(X,Y)$。

样例

样例输入 1

3 6 2 2
1 4 6

样例输出 1

1

提示

【样例说明】

可以将序列变换为 2 4 6 或者 1 3 5。前者变换代价为 $1$，后者为 $2$。因此最小 TransformCost 为 $1$。

【数据规模】

对于10%的数据，$N≤100,Q≤10000,1≤A,B≤100$。

对于30%的数据，$N≤10000,Q≤10000,1≤A,B≤100$。

对于60%的数据，$N≤10000,Q≤10^9,1≤A,B≤Q$。

对于100%的数据，$N≤500000,Q≤10^9,1≤A,B≤Q$。