修整数列

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 seq.in 输出文件 seq.out

【题目描述】

有一个长度为n的数列c_i，我们每次可以执行一个下面的操作之一:

1.选择一个区间[l,r]，区间内每个数加上a

2.选择一个区间[l,r]，区间内每个数减去a

3.选择一个区间[l,r]，区间内每个数加上b

4.选择一个区间[l,r]，区间内每个数减去b

现在想用最少的操作次数使得数列的每个元素都变为0，请你计算出最少的操作次数

【输入格式】

第一行三个整数n，a，b，含义如题目所示

接下来一行n个整数，表示数列c_i

【输出格式】

一行一个整数，表示最少的操作次数。如果没有可行方案，直接输出-1

【样例输入】

5 2 3

1 2 1 1 -1

【样例输入】

5

【数据规模】

对于30%的数据，1 <= n,a,b <= 200, -200 <= c_i <= 200

对于60%的数据，1 <= n,a,b <= 2000, -2000 <= c_i <= 2000

对于100%的数据，1 <= n <= 100000, 1 <= a, b <= 10^9, -10^9 <= c_i <= 10^9

【时限】

2s