题目描述
译自 POI 2012 Stage 3. Day 1「Leveling Ground」
给定一个长度为 n 的数组,每次操作可以将一个区间的数增加或减少 a,或将一个区间的数增加或减少 b。求使整个数组变为 0 的最小操作次数。若无解请输出 −1。
输入格式
第一行三个整数 n,a,b(1≤n≤100 000,1≤a,b≤109)。
接下来一行 n 个整数 h1,h2,…,hn,绝对值均不超过 109。
输出格式
输出一行一个整数,表示最小操作次数。
样例
5 2 3
1 2 1 1 -1
5
一种操作方案是:
- 将前两个数加 2;
- 将前两个数减 3;
- 将后四个数加 2;
- 将最后一个数加 2;
- 将后四个数减 3。
数据范围与提示
对于 30% 的数据,n,a,b≤200,−200≤h1,h2,…,hn≤200.
对于 60% 的数据,n,a,b≤2000,−2000≤h1,h2,…,hn≤2000.
对于 90% 的数据,a,b≤106.
对于所有数据,1≤n≤100 000,1≤a,b≤109.