POJ-3171 : Cleaning Shifts

問題概要

n個の重み付き区間[a[i],b[i]), w[i]が与えられる。[M,E]を全て被覆するのに必要な最小コストを求める問題。n<10^4。

解法

これとほとんど同じ。座標圧縮すれば定数を多少軽くできる。

acceptされたコード

#include <cstdio>
#include <vector>
using namespace std;

typedef long long int64;

const int64 INF = (1LL<<62) - 2;

const int MAX_N = (int)(1e4);
const int MAX_T = 86400;

int N, M, E;
vector< pair<int,int> > rs[MAX_T]; //(end, cost)

void init() {
	scanf("%d%d%d", &N, &M, &E);
	++E;
	for (int _ = 0; _ < N; ++_) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		++y;
		if (y <= M || x >= E) {
			continue;
		}
		x = max(x, M);
		y = min(y, E);
		rs[x].push_back(make_pair(y, z));
	}
}

int64 solve() {
	rmq.init(MAX_T + 2);
	rmq.update(E, 0);
	for (int i = E; i >= M; --i) {
		for (int j = 0; j < (int)rs[i].size(); ++j) {
			rmq.update(i, min(rmq.getElement(i), rmq.getValue(i, rs[i][j].first + 1) + rs[i][j].second));
		}
	}
	int64 ans = rmq.getElement(M);
	return ans >= INF ? -1 : ans;
}

int main() {
	init();
	printf("%lld\n", solve());

	return 0;
}