[CTSC2009] 序列变换
题目描述
给定一个整数序列X1,X2,X3,...,Xn和三个正整数 Q,A,B 满足:
○ 1≤Xi≤Q 对于任意 1≤i≤n;
○ Xi≤Xi+1 对于任意 1≤i<n;
○ A≤n−1Q−1 且 A≤B。
对于任意 1≤i≤n,做如下变换:Yi=Xi+δi,其中δi是一个整数。使得新序列 Y满足如下性质:
○ 1≤Yi≤Q 对于任意 1≤i≤n;
○ Yi+1−Yi∈[A,B] 对于任意 1≤i<n。
对于这样一个变换,所需代价定义为TransformCost(X,Y)=∑i=1n∣δi∣
本题的任务即为寻找一个变换,使得TransformCost(X,Y)最小化。
输入格式
输入文件 sequence.in 包含两行。第一行 4 个整数, N,Q,A,B。接下来一行包含 N 个整数,分别为 X1,X2,X3,...,Xn 。
输出格式
输出文件 sequence.out 仅包含一行,为最小的TransformCost(X,Y)。
样例 #1
样例输入 #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≤109,1≤A,B≤Q。
对于 100%的数据, N≤500000,Q≤109,1≤A,B≤Q。