java - 该算法拼图代码(USACO)的良好解决方案？

Question

我是计算机科学专业的一年级学生，目前正在参加一些算法竞赛。我编写的以下代码存在一个缺陷，我不确定如何修复

这是问题说明:
http://www.usaco.org/index.php?page=viewproblem2&cpid=811

在声明中，我想念农夫约翰只能在两个靴子都可以站立的瓷砖上切换靴子的地方。我尝试在不同的地方添加约束，但是似乎没有一个可以完全解决该问题。我真的看不出没有屠杀代码的方法

基本上，问题在于John一直在无法站立新靴子的瓷砖上切换靴子，而我似乎无法修复它

这是我的代码(抱歉一个字母的变量):

import java.io.*;
import java.util.*;
public class snowboots {
    static int n,k;
    static int[] field,a,b; //a,b --> strength, distance
    static int pos;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("snowboots.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("snowboots.out")));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        field = new int[n];
        a = new int[k];
        b = new int[k];
        for (int i = 0; i < n; i++)
            field[i] = Integer.parseInt(st.nextToken());
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            a[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
        }

        pw.println(solve());
        pw.close();

    }
    static int solve() {
        pos = 0;
        int i = 0; //which boot are we on?
        while(pos < n-1) {

            while(move(i)); //move with boot i as far as possible

            i++; //use the next boot

        }
        i--;
        return i;
    }
    static boolean move(int c) {
        for (int i = pos+b[c]; i > pos; i--) {
            if (i < n && field[i] <= a[c]) { //snow has to be less than boot strength
                pos = i;
                return true;
            }
        }
        return false;
    }
}

我尝试在“移动”方法中添加一个约束，并在更新I时添加一个约束，但是它们都过于严格，并且会在不需要的时间激活

可以挽救吗？

Answer 1

是的，可以通过添加额外的for -loop来挽救您的解决方案。

您需要做的是，如果您发现前一双靴子可以一直带到下一个雪地太深的地砖，那么您需要尝试“回溯”到不太合适的最新地砖深。最终给出了在最坏情况下O(N·B)时间和O(1)额外空间的解决方案。

为何回溯到该图块可能还不是很清楚-毕竟，仅仅是因为您可以到达给定的图块，这并不一定意味着您能够在此之前到达所有图块-所以让我解释一下为什么还可以。

令maxReachableTileNum为您先前启动时可以到达的最后一个图块的编号(1到N之间)，令lastTileNumThatsNotTooDeep为maxReachableTileNum或之前的最后一个图块的编号(1到N之间)，但不要太深下一场雪覆盖。 (我们知道有这样一个图块，因为图块＃1根本没有积雪，所以如果没有别的事情，我们知道我们可以追溯到一开始。)现在，由于我们能够到达maxReachableTileNum，因此可以使用某些引导必须要么踩过lastTileNumThatsNotTooDeep(在这种情况下，没问题，就可以到达)，要么跳过它到以后的某个磁贴(在maxReachableTileNum上或之前)。但是后面的图块必须比lastTileNumThatsNotTooDeep更深(因为后面的图块的深度大于s currentBootNum，后者至少与lastTileNumThatsNotTooDeep的深度一样大)，这意味着跳过lastTileNumThatsNotTooDeep的启动确实可以踩到lastTileNumThatsNotTooDeep了:这将意味着比实际覆盖的内容要更短一步(OK)到覆盖较浅的图块(OK)上。因此，无论哪种方式，我们都知道lastTileNumThatsNotTooDeep是可访问的。因此，对我们来说，回溯到lastTileNumThatsNotTooDeep是安全的。 (注意:以下代码使用名称reachableTileNum而不是lastTileNumThatsNotTooDeep，因为它继续使用reachableTileNum变量向前搜索以找到可到达的图块。)

但是，我们仍然必须保留以前的maxReachableTileNum:可能无法进行回溯(因为它可能无法使我们取得比已有的进一步进步)，在这种情况下，我们将丢弃这些引导，并且移至下一个对，其上一个值为maxReachableTileNum。

因此，总的来说，我们有:

public static int solve(
    final int[] tileSnowDepths,           // tileSnowDepths[0] is f_1
    final int[] bootAllowedDepths,        // bootAllowedDepths[0] is s_1
    final int[] bootAllowedTilesPerStep   // bootAllowedTilesPerStep[0] is d_1
) {
    final int numTiles = tileSnowDepths.length;
    final int numBoots = bootAllowedDepths.length;
    assert numBoots == bootAllowedTilesPerStep.length;

    int maxReachableTileNum = 1; // can reach tile #1 even without boots

    for (int bootNum = 1; bootNum <= numBoots; ++bootNum) {
        final int allowedDepth = bootAllowedDepths[bootNum-1];
        final int allowedTilesPerStep = bootAllowedTilesPerStep[bootNum-1];

        // Find the starting-point for this boot -- ideally the last tile
        // reachable so far, but may need to "backtrack" if that tile is too
        // deep; see explanation above of why it's safe to assume that we
        // can backtrack to the latest not-too-deep tile:

        int reachableTileNum = maxReachableTileNum;
        while (tileSnowDepths[reachableTileNum-1] > allowedDepth) {
            --reachableTileNum;
        }

        // Now see how far we can go, updating both maxReachableTileNum and
        // reachableTileNum when we successfully reach new tiles:

        for (int tileNumToTry = maxReachableTileNum + 1;
             tileNumToTry <= numTiles
                 && tileNumToTry <= reachableTileNum + allowedTilesPerStep;
             ++tileNumToTry
        ) {
            if (tileSnowDepths[tileNumToTry-1] <= allowedDepth) {
                maxReachableTileNum = reachableTileNum = tileNumToTry;
            }
        }

        // If we've made it to the last tile, then yay, we're done:

        if (maxReachableTileNum == numTiles) {
            return bootNum - 1; // had to discard this many boots to get here
        }
    }

    throw new IllegalArgumentException("Couldn't reach last tile with any boot");
}

(我在USACO的示例数据上对此进行了测试，并按预期返回了 2。)

这可以潜在地被进一步优化，例如。使用逻辑来跳过对靴子显然无济于事的靴子(因为它们既不比以前的成功靴子更结实，也不敏捷)，或者具有额外的数据结构来跟踪最新的最小值(优化回溯)流程)，或避免回溯的逻辑超出了想象的有用范围；但考虑到N·B≤2502 = 62,500，我认为没有必要进行任何此类优化。

编辑为添加(2019-02-23):我已经作了进一步的考虑，我想到实际上可以在最坏的O(N + BlogN)时间(即渐近优于O(N·B))和O(N)的额外空间。但这要复杂得多。它涉及三种额外的数据结构(一种跟踪最新最小值的位置，以允许在O(logN)时间内回溯;一种跟踪 future 最小值的位置，以允许在O(logN)中进行检查如果回溯实际上是有帮助的(如果可以，则前进到相关的最小值)；并且保持必要的前瞻性信息以使第二个保持 amortized O(1)时间)。解释为什么要保证该解决方案在O(N + BlogN)时间之内也很复杂(因为它涉及很多 amortized analysis，并做了一些细微的更改，看起来像是一种优化，例如，用替换线性搜索二进制搜索-可能会破坏分析，并实际上增加了最坏情况下的时间复杂度，因为已知N和B最多都为250，所以我认为所有复杂性都不值得。