题目: CF13451

洛谷还没更新。

感觉已经和别人的AC代码调得很像了。。。

WA on #3

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<set>
#include<cstdlib>
#include<cctype>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 1e4 + 5;
const ll maxm = 1e3 + 5;
template<class T>
inline T qread(T &IEE){
	register T x = 0, f = 1;
	register char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-'){
			f = -f;
		}
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return IEE = x * f;
}
template<class T>
inline void qwrite(T a){
	if(!a){
		putchar('0');
		return ;
	}
 	if(a < 0){
		putchar('-');
		a = -a;
	}
	if(a > 9) qwrite(a / 10);
	putchar(a % 10 + 48);
	return ;
}
template<class T>
inline T ab(T a){
	return (a > 0) ? a : -a;
}
template<class T>
inline void swa(T &a, T &b){
	a ^= b ^= a ^= b;
	return ;
}
ll ans, v, tmp, dis, u, r, g, m, n;
ll a[maxn];
ll dp[maxn][maxm];
struct node{
	ll id, val;
	node(ll dd = 0, ll vv = 0){
		id = dd;
		val = vv;
	}
};
queue<node> q;
int main(){
//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		cin >> a[i];
	}
	cin >> g >> r;
//	qread(g);
//	qread(r);
	sort(a + 1, a + m + 1);
	memset(dp, -1, sizeof(dp));
	q.push(node(1, 0));
	dp[1][0] = 0;
	ans = 0x3f3f3f3f;
	while(!q.empty()){
		node fr = q.front();
		q.pop();
		v = fr.val, u = fr.id;
		if(u == m){
			if(v == 0){
				ans = min(ans, dp[m][v] * (g + r) - r);
			} else {
				ans = min(ans, dp[m][v] * (g + r) + v);
			}
			continue;
		}
		dis = a[u + 1] - a[u];
		if(v + dis < g && dp[u + 1][v + dis] == -1){
			dp[u + 1][v + dis] = dp[u][v];
			q.push(node(u + 1, v + dis));
		} 
		if(v + dis == g && dp[u + 1][0] == -1){
			dp[u + 1][0] = dp[u][v] + 1;
			q.push(node(u + 1, 0));
		}
		if(u >= 1){
			dis = a[u] - a[u - 1];
			if(v + dis < g && dp[u - 1][v + dis] == -1){
				dp[u - 1][v + dis] = dp[u][v];
				q.push(node(u - 1, v + dis));
			} 
			if(v + dis == g && dp[u - 1][0] == -1){
				dp[u - 1][0] = dp[u][v] + 1;
				q.push(node(u - 1, 0));
			}
		}
	}
	if(ans == 0x3f3f3f3f){
		puts("-1");
		return 0;
	}
	cout << ans << endl;
	return 0;
}