## Patches

### 题目描述

Carlos is very concerned with the environment. Whenever possible, he tries to use less pollutingmeans of transport. He recently got a job close to home and is now using his bike to go to work.
Unfortunately, in the route between his home and his job there is a nail factory, and often somenails fall from their trucks, and end up puncturing Carlos’ bike tires. Therefore he ends up having tomake several patches on the tires of his bike.
To make the repairs, Carlos uses two different types of patches. Both types are as wide as a biketire, but differ in length. As the cost of the patch is proportional to its length, Carlos is trying to finda way to save money, using the least possible length of patches to make the repairs, without cuttingthe patches.
The first step in repairing a tire is making a chalk mark on a position of the tire and then writingdown the distances, measured clockwise, of each of the holes in relation to the chalk mark. Each holemust be completely covered by a patch. Carlao would like your help to determine, given the positionsof the holes, the most economic way to make the repair.

### 输入格式

The input contains two lines. The first line contains four integers $N, C, T_1\ e\ T_2$. Integer $N$ indicates the number of holes in the tire, and $C$ indicates the cirunference length of the tire, in centimeters.
The lengths of the patches in centimeters are given by integers $T_1$ and $T_2$. The second line contains $N$ integers $F_i$, representing the distance, in clockwise direction, from the chalk mark to hole $i$, in centimeters.

### 输出格式

Your program must print a single line, containing a single integer, the smallest total length of patches needed to make all the repairs.

### 样例输入1

5 20 2 3
2 5 8 11 15


### 样例输出1

8


### 样例输入2

4 20 12 9
1 2 3 13


### 样例输出2

12


### 数据范围

• $1 \le N \le 1000$
• $1 \le C \le 10^6$
• $1 \le T_1, T_2 \le C$
• $0 \le F_i \le C-1, 1 \le i \le N$
• If the distance between two holes is exactly $k$ centimeters, a patch of length $k$ centimeters covers both holes.

## 题解

#include<bits/stdc++.h>
using namespace std;
int n,c;
int t1,t2;
int dp[2009];
int a[2009];
int l1,l2;
int ans;
int main(){
scanf("%d%d",&n,&c);
scanf("%d%d",&t1,&t2);
for(int j=1;j<=n;j++)
scanf("%d",&a[j]);
for(int p=1;p<=n;p++){
l1=l2=p;
memset(dp,0,sizeof(dp));
dp[p]=min(t1,t2);
for(int j=p+1;j<n+p;j++){
while(a[j]-a[l1]>t1) l1++;
while(a[j]-a[l2]>t2) l2++;
dp[j]=min(dp[l1-1]+t1,dp[l2-1]+t2);
}
if(p==1) ans=dp[n];
ans=min(ans,dp[n+p-1]);
a[n+p]=a[p]+c;
}
printf("%d",ans);
return 0;
}