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