algorithm - 动态规划 : USACO Optimal Milking

Question

我一直在看一些USACO黄金级别的算法问题，我需要有人帮我解释一下这个问题的解决方案。 Here是问题所在，解决方案如下:

Usually the first step in solving incremental-update problems is to solve the problem without the incremental updates, but in this case it can lead one up a blind alley. There is a quite simple DP solution to the non-incremental version of this problem, but it is not at all obvious how to incrementally update this in less than linear time.

Instead, we can find a divide-and-conquer DP solution that will be easier to update. Divide the range in half, and in each half solve the problem again. In fact, we solve four variants of the problem, depending on whether the left and/or right endpoint is allowed to be used. Given these results from the two halves, we can easily combine them to form the results for the whole range. The ranges form a segment tree over the barn, where each tree node depends on its two children, and the answer is held at the root of the tree.

Given this tree structure, it is now clear how we can make incremental updates in O(log N) time: an update affects a leaf of the tree, which in turn requires its O(log N) ancestors to be updated.

这个解决方案没有代码，我也不太明白如何实现这个想法。如果有人能更彻底地解释它或告诉我如何编码，我将不胜感激。

编辑:

我现在更好地理解了解决方案的意思，并且编写了一个解决方案。但是，该代码仅适用于前两个测试数据。我以为我按照他们所说的编写了程序，但我一定是犯了一个错误。这是我的代码(在 Java 中):

import java.io.File;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Created by jameslennon on 1/19/14.
 */
public class optmilk {
    static int n, d;
    static int[] m, indx;
    static node[] tree;

    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(new File("optmilk.in"));
        PrintWriter out = new PrintWriter(new FileWriter("optmilk.out"));
        n = in.nextInt();
        m = new int[n];
        indx = new int[n];
        d = in.nextInt();
        tree = new node[1 << n + 1];
        for (int i = 0; i < n; i++) {
            m[i] = in.nextInt();
        }
        construct(1, 0, n - 1);
        int r = 0;
        for (int i = 0; i < d; i++) {
            int a = in.nextInt() - 1, b = in.nextInt();
            update(a, b);
            m[a] = b;
            r += max(tree[1].none, tree[1].both, tree[1].left, tree[1].right);
        }
        //System.out.println(r);
        out.println(r);
        out.close();
        System.exit(0);
    }

    private static void update(int a, int b) {
        int i = indx[a];
        int w = 1;
        tree[i].both = b;
        i /= 2;
        while (true) {
            update_node(i, w);
            w *= 2;
            if (i == 1) break;
            i /= 2;
        }
    }

    private static int max(int... a) {
        int max = Integer.MIN_VALUE;
        for (int b : a) {
            max = Math.max(max, b);
        }
        return max;
    }

    private static void update_node(int i, int w) {
        if (w == 1) {
            tree[i].left = tree[2 * i].both;
            tree[i].right = tree[2 * i + 1].both;
        } else {
            tree[i].none = max(tree[2 * i].none + tree[2 * i + 1].none, tree[2 * i].right + tree[2 * i + 1].none, tree[2 * i].none + tree[2 * i + 1].left);
            tree[i].right = max(tree[2 * i].none + tree[2 * i + 1].right, tree[2 * i].right + tree[2 * i + 1].right, tree[2 * i].none + tree[2 * i + 1].both);
            tree[i].left = max(tree[2 * i].left + tree[2 * i + 1].none, tree[2 * i].both + tree[2 * i + 1].none, tree[2 * i].left + tree[2 * i + 1].left);
            tree[i].both = max(tree[2 * i].left + tree[2 * i + 1].right, tree[2 * i].both + tree[2 * i + 1].right, tree[2 * i].left + tree[2 * i + 1].both);
        }
    }

    private static void construct(int i, int a, int b) {
        if (b - a == 0) {
            indx[a] = i;
            tree[i] = new node(0, 0, 0, m[a]);
            return;
        }
        construct(2 * i, a, (a + b) / 2);
        construct(2 * i + 1, (a + b) / 2 + 1, b);
        int both = max(tree[2 * i].left + tree[2 * i + 1].right, tree[2 * i].both + tree[2 * i + 1].right, tree[2 * i].left + tree[2 * i + 1].both);
        if (b - a == 1) both = 0;
        tree[i] = new node(max(tree[2 * i].none + tree[2 * i + 1].none, tree[2 * i].right + tree[2 * i + 1].none, tree[2 * i].none + tree[2 * i + 1].left),
                max(tree[2 * i].none + tree[2 * i + 1].right, tree[2 * i].right + tree[2 * i + 1].right, tree[2 * i].none + tree[2 * i + 1].both),
                max(tree[2 * i].left + tree[2 * i + 1].none, tree[2 * i].both + tree[2 * i + 1].none, tree[2 * i].left + tree[2 * i + 1].left),
                both);
    }

    static class node {
        int none, right, left, both;

        public node(int n, int r, int l, int b) {
            none = n;
            right = r;
            left = l;
            both = b;
        }
    }
}

Answer 1

哪一部分你不明白？

第一段说当没有更新时有一个简单的解决方案(即如果农民不进行维护，每天提取相同数量的牛奶。这个数量可以使用 DP 计算)。

第二段说有一个分而治之的解决方案，当机器容量发生变化时更容易更新。它还提供了解决方案的概要。