Cleaning Shifts (POJ 3171)
This is a range covering problem with dynamic programming solutions. But as to improve the time efficiency, we have to make use of segment tree to handle the minimum value of a range.
At first we sort the cows by their start range point. Then from the first cow and its available range
[l, r]
, we query the least possible cost with previous cows and the end points of their work period
ends in [l - 1, r - 1]
, with the least possible cost in that range we can calculate the least cost
if we pick add cow to work. Then we keep the minimum value at time point r
. Then the cost value at E
will be the final answer. We should return -1
if that value is Integer.MAX_VALUE
because that means
there is no way to cover the whole time span.
import java.io.*;
import java.util.*;
public class CleaningShifts {
private static void set(int[] rmq, int i, int v, int k, int kl, int kr) {
if (i >= kl && i <= kr) {
rmq[k] = Math.min(rmq[k], v);
if (kl >= kr) return;
int mid = (kl + kr) >> 1;
set(rmq, i, v, k * 2 + 1, kl, mid);
set(rmq, i, v, k * 2 + 2, mid + 1, kr);
}
}
private static int query(int[] rmq, int l, int r, int k, int kl, int kr) {
if (l > kr || r < kl) return Integer.MAX_VALUE;
else if (l <= kl && r >= kr) {
return rmq[k];
} else {
int mid = (kl + kr) >> 1;
return Math.min(
query(rmq, l, r, k * 2 + 1, kl, mid),
query(rmq, l, r, k * 2 + 2, mid + 1, kr));
}
}
private static void solve(int T, int[][] cows) {
int L = 1;
while (L < T) L <<= 1;
int[] rmq = new int[L * 2 - 1];
Arrays.fill(rmq, Integer.MAX_VALUE);
Arrays.sort(cows, new Comparator<int[]>() {
public int compare(int[] a, int b[]) {
if (a[0] != b[0]) return a[0] - b[0];
else return a[1] - b[1];
}
});
for (int i = 0; i < cows.length; i++) {
int l = cows[i][0], r = cows[i][1], s = cows[i][2];
int rangemin = 0;
if (l > 0) rangemin = query(rmq, l - 1, r - 1, 0, 0, L - 1);
if (rangemin < Integer.MAX_VALUE) {
set(rmq, r, rangemin + s, 0, 0, L - 1);
}
}
int min = rmq[L + T - 2];
if (min == Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(min);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int N = in.nextInt(), M = in.nextInt(), E = in.nextInt();
int T = E - M + 1;
int[][] cows = new int[N][3];
for (int i = 0; i < N; i++) {
for (int j = 0; j < 3; j++) {
cows[i][j] = in.nextInt();
}
cows[i][0] -= M;
cows[i][1] -= M;
}
solve(T, cows);
}
}
}