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; }