PKU 3171 - Cleaning Shifts

問題文 : Cleaning Shifts

解法 :
dp[Ei] -> Ei秒まで掃除するのに必要な時間, とし, 牛iが時間Si秒からEi秒まで掃除でき, 雇うのに給料がMiかかるとすると
dp[Ei] = min(dp[Ei], min(dp[Si] ~ dp[Ei]) + Mi)
となる. dpテーブルはINFなどで初期化しておく.
このとき, dpテーブルはすべてうめずに, 牛が掃除を終わる時間についてだけ埋めれば良いことに注意する.
Ei - Siは大きくなる可能性があるため, Ei - Siの平均をTとし, 牛の頭数をNとすると, O(NT)時間になってしまう.
しかし, dp[Si] ~ dp[Ti]までの最小値を求めるのにRMQを使うことで, 計算量をO(NlogT)時間に落とすことができる.

このとき, E秒まで掃除できなければ, dp[E]がINFになっているはずなので, -1を出力する.

コード :

#include <cstdio>
#include <algorithm>

#define INF (1 << 29)

using namespace std;

typedef struct {
	int s, e, m;
} Cow;

int seg[1 << 18];
int size;

void init(int n)
{
	size = 1;
	while (size < n) size *= 2;
	
	for (int i = 0; i < 2 * size; i++){
		seg[i] = INF;
	}
}

void update(int k, int x)
{
	k += size - 1;
	
	seg[k] = x;
	
	while (k){
		k = (k - 1) / 2;
		seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
	}
}

int getMin(int a, int b, int k, int l, int r)
{
	if (b <= l || r <= a){
		return (INF);
	}
	
	if (a <= l && r <= b){
		return (seg[k]);
	}
	int lch = getMin(a, b, k * 2 + 1, l, (l + r) / 2);
	int rch = getMin(a, b, k * 2 + 2, (l + r) / 2, r);
	
	return (min(lch, rch));
}

bool operator < (const Cow &a, const Cow &b)
{
	return (a.s < b.s);
}

int main()
{
	int N, M, E;
	Cow data[10000];
	
	scanf("%d %d %d", &N, &M, &E);
	E -= M;
	
	for (int i = 0; i < N; i++){
		scanf("%d %d %d", &data[i].s, &data[i].e, &data[i].m);
		data[i].s = max(0, data[i].s - M) + 1;
		data[i].e = max(0, data[i].e - M) + 1;
	}
	init(E + 1);
	
	update(0, 0);
	
	sort(data, data + N);
	
	for (int i = 0; i < N; i++){
		update(data[i].e, min(seg[data[i].e + size - 1], getMin(data[i].s - 1, data[i].e + 1, 0, 0, size) + data[i].m));
	}
	
	printf("%d\n", seg[E + size] == INF ? -1 : seg[E + size]);
	
	return (0);
}