#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits>
#include <queue>//!!!优先队列优化算法

using namespace std;

typedef struct FX
{
	FX(int i = 0, int v = 0) :index(i), val(v) {};

	int index;
	int val;
}FX;

bool operator<(const FX &f1, const FX &f2)//优先队列比较
{
	return f1.val < f2.val;
}

int dp[1000010];
int haveCow[1000010];
priority_queue<FX> fx;

int main()
{
	int N, L, A, B;
	
	while (cin >> N >> L >> A >> B)
	{
		//初始化
		for (int i = 0; i <= L; ++i)
			dp[i] = -1;
		memset(haveCow, 0, sizeof(haveCow));
		while (!fx.empty())//清空队列
			fx.pop();

		for (int i = 0; i < N; ++i)
		{
			int s, e;
			cin >> s >> e;
			for (int j = s + 1; j < e; ++j)
				haveCow[j] = 1;
		}

		dp[0] = 0;
		for (int i = 2 * A; i <= L; i += 2)//小于2*A的范围都不可达 奇数都不可达
		{
			int tmpIndex = i - 2 * A;//每次入队的下标:最近的有效点
			if (dp[tmpIndex] != -1)
				fx.push(FX(tmpIndex, dp[tmpIndex]));

			if (!haveCow[i] && !fx.empty())
			{
				while (!fx.empty() && fx.top().index < i - 2 * B)//不在有效范围内的解出队
					fx.pop();

				if (!fx.empty())
					dp[i] = fx.top().val + 1;
			}
		}

		cout << dp[L] << endl;
	}

	return 0;
}

• Re:求测试数据 一时半会儿看不出来哪里错 (31) 20152430102 2017-04-17 22:00:40