#3297. [CTSC2009] 序列变换

[CTSC2009] 序列变换

[CTSC2009] 序列变换

题目描述

给定一个整数序列X1,X2,X3,...,XnX_1, X_2, X_3, ... ,X_n和三个正整数 Q,A,BQ, A, B 满足:

1XiQ1 \leq X_i \leq Q 对于任意 1in1 \leq i \leq n

XiXi+1X_i \leq X_{i+1} 对于任意 1i<n1 \leq i < n

AQ1n1A \leq \frac{Q-1}{n-1}ABA \leq B

对于任意 1in1 \leq i \leq n,做如下变换:Yi=Xi+δiY_i = X_i + \delta_i,其中δi\delta_i是一个整数。使得新序列 YY满足如下性质:

1YiQ1 \leq Y_i \leq Q 对于任意 1in1 \leq i \leq n

Yi+1Yi[A,B]Y_{i+1} - Y_i \in [A, B] 对于任意 1i<n1 \leq i < n

对于这样一个变换,所需代价定义为TransformCost(X,Y)=i=1nδiTransformCost(X, Y) = \sum_{i = 1}^{n}{|\delta_i|}

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

输入格式

输入文件 sequence.in 包含两行。第一行 44 个整数, N,Q,A,BN, Q, A, B。接下来一行包含 NN 个整数,分别为 X1,X2,X3,...,XnX_1, X_2, X_3, ... , X_n

输出格式

输出文件 sequence.out 仅包含一行,为最小的TransformCost(X,Y)TransformCost(X, Y)

样例 #1

样例输入 #1

3 6 2 2
1 4 6

样例输出 #1

1

提示

样例说明

可以将序列变换为 2 4 62\ 4\ 6 或者 1 3 51\ 3\ 5。前者变换代价为 11,后者为 22。因此最小TransformCostTransformCost11

数据规模

对于 1010%的数据 , N100,Q10000,1A,B100N \leq 100, Q \leq 10000, 1\leq A, B \leq 100

对于 3030%的数据 , N10000,Q10000,1A,B100N \leq 10000, Q \leq 10000, 1\leq A, B \leq 100

对于 6060%的数据 , N10000,Q109,1A,BQN \leq 10000, Q \leq 10^9, 1\leq A, B \leq Q

对于 100100%的数据, N500000,Q109,1A,BQN \leq 500000, Q \leq 10^9, 1\leq A, B \leq Q