POJ 3171 Cleaning Shifts​ 题解 《挑战程序设计竞赛》

POJ 3171 Cleaning Shifts

铲屎官：约翰希望在时间[M,E]内保持牛舍始终有牛在打扫，有N头牛分别愿意在时间[T1,T2]内打扫并收工钱S。求最小花费。

3.4熟练掌握动态规划

利用数据结构高效求解

是POJ 2376 Cleaning Shifts的升级版，赋予了每个区间[start_i,end_i]权重salary_i。定义dp[end_i]表示在end_i秒内的最小花费，有dp[0]=0。

dp[end_i] =  min(dp[end_i], min(dp[start_i] ~ dp[end_i]) + salary_i)

涉及到区间最小值min(dp[start_i] ~ dp[end_i])，可以用RangeMinimumQuery高效（O(logT)）地解决问题。

#include <cstdio>
#include <algorithm>

using namespace std;
#define MAX_N  10000 + 16

struct RangeMinimumQuery
{
	int size;
	int dat[1 << 18];

	void init(int n)
	{
		size = 1;
		while (size < n)
		{
			size *= 2;
		}
		memset(dat, 0x3f, sizeof(int) * size * 2);
	}

	// set value[k] = a
	void update(int k, int a)
	{
		k += size - 1;
		dat[k] = a;
		while (k > 0)
		{
			k = (k - 1) / 2;
			dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
		}
	}

	// min of range[a,b)
	int query(int a, int b, int k, int l, int r)
	{
		if (r <= a || b <= l)
			return 0x3f3f3f3f;
		if (a <= l && r <= b)
			return dat[k];
		return min(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
	}

	// min of range[a,b)
	int query(int a, int b)
	{
		return query(a, b, 0, 0, size);
	}

	// get value[k]
	int get(int k)
	{
		return dat[k + size];
	}
} rmq;

struct Cow
{
	int start, end, salary;
	const bool operator < (const Cow &other)
	{
		return start < other.start;
	}
};
Cow cow[MAX_N];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N, M, E;
	scanf("%d %d %d", &N, &M, &E);
	E -= M;

	for (int i = 0; i < N; ++i)
	{
		scanf("%d %d %d", &cow[i].start, &cow[i].end, &cow[i].salary);
		cow[i].start = max(0, cow[i].start - M) + 1;
		cow[i].end = max(0, cow[i].end - M) + 1;
	}
	rmq.init(E + 1);
	rmq.update(0, 0);

	sort(cow, cow + N);

	for (int i = 0; i < N; ++i)
	{
		rmq.update(cow[i].end, min(rmq.get(cow[i].end - 1), rmq.query(cow[i].start - 1, cow[i].end + 1) + cow[i].salary));
	}

	printf("%d\n", rmq.get(E) == 0x3f3f3f3f ? -1 : rmq.get(E));

#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3171 Cleaning Shifts​ 题解 《挑战程序设计竞赛》