Yogurt Factory (POJ 2393)

To apply greedy strategy, we decide production at one day when it is needed in the future instead of deciding it in ahead of time. Let's say we are at week now and we need to deliver units of yogurt, then we always pick the most save week to produce this amount of yogurt in week . The cost of each week will be

To find the lowest cost by traversing all weeks before is not acceptable. It cost too much time. But let't dig into the formular above more deeper, we will find that the lowest the in won't decrease when we are pushing forward. What's more. If we are at and where , then for any future weeks we always have

So in the th week we can verify if current is more save and update the most save week according to the result.

import java.io.*;
import java.util.*;

public class YogurtFactory {
    private static void solve(long[][] weeks, int S) {
        long cost = 0;
        int lw = 0;
        for (int i = 0; i < weeks.length; i++) {
            if ((weeks[lw][0] + S * (i - lw)) > weeks[i][0]) lw = i;
            cost += (weeks[lw][0] + S * (i - lw)) * weeks[i][1];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(), S = in.nextInt();
        long[][] weeks = new long[N][2];
        for (int i = 0; i < N; i++) {
            weeks[i][0] = in.nextLong();
            weeks[i][1] = in.nextLong();
        solve(weeks, S);