Хорошее решение для этого алгоритмического кода головоломки (USACO)?

Один из способов решить эту проблему с помощью BFS. Вы можете ссылаться на код ниже для деталей. Надеюсь, это поможет.

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

public class SnowBoots {

    public static int n;
    public static int[] deep;
    public static int nBoots;
    public static Boot[] boots;

    public static void main(String[] args) throws Exception {

        // Read the grid.
        Scanner stdin = new Scanner(new File("snowboots.in"));

        // Read in all of the input.
        n = stdin.nextInt();
        nBoots = stdin.nextInt();
        deep = new int[n];
        for (int i = 0; i < n; ++i) {
            deep[i] = stdin.nextInt();
        }
        boots = new Boot[nBoots];
        for (int i = 0; i < nBoots; ++i) {
            int d = stdin.nextInt();
            int s = stdin.nextInt();
            boots[i] = new boot(d, s);
        }

        PrintWriter out = new PrintWriter(new FileWriter("snowboots.out"));
        out.println(bfs());
        out.close();
        stdin.close();
    }

    // Breadth First Search Algorithm [https://en.wikipedia.org/wiki/Breadth-first_search]
    public static int bfs() {

        // These are all valid states.
        boolean[][] used = new boolean[n][nBoots];
        Arrays.fill(used[0], true);

        // Put each of these states into the queue.
        LinkedList<Integer> q = new LinkedList<Integer>();
        for (int i = 0; i < nBoots; ++i) {
            q.offer(i);
        }

        // Usual bfs.
        while (q.size() > 0) {

            int cur = q.poll();
            int step = cur / nBoots;
            int bNum = cur % nBoots;

            // Try stepping with this boot...
            for (int i = 1; ((step + i) < n) && (i <= boots[bNum].maxStep); ++i) {
                if ((deep[step+i] <= boots[bNum].depth) && !used[step+i][bNum]) {
                    q.offer(nBoots * (step + i) + bNum);
                    used[step + i][bNum] = true;
                }
            }

            // Try switching to another boot.
            for (int i = bNum + 1; i < nBoots; ++i) {
                if ((boots[i].depth >= deep[step]) && !used[step][i]) {
                    q.offer(nBoots * step + i);
                    used[step][i] = true;
                }
            }
        }

        // Find the earliest boot that got us here.
        for (int i = 0; i < nBoots; ++i) {
            if (used[n - 1][i]) {
                return i;
            }
        }

        // Should never get here.
        return -1;
    }
}

class Boot {

    public int depth;
    public int maxStep;

    public Boot(int depth, int maxStep) {
        this.depth = depth;
        this.maxStep = maxStep;
    }
}

Вы можете решить эту проблему с помощью динамического программирования. Вы можете увидеть концепцию в этой ссылке (просто прочитайте раздел «Компьютерное программирование»). Он имеет следующие два шага.

• Сначала решите проблему рекурсивно.
• Помните состояния.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mx 100005
#define mod 1000000007
int n, b;
int f[333], s[333], d[333];
int dp[251][251];
int rec(int snowPos, int bootPos)
{
    if(snowPos == n-1){
        return 0;

    int &ret = dp[snowPos][bootPos];
    if(ret != -1) return ret;
    ret = 1000000007;
    for(int i = bootPos+1; i<b; i++)
    {
        if(s[i] >= f[snowPos]){
            ret = min(ret, i - bootPos + rec(snowPos, i));
        }
    }
    for(int i = 1; i<=d[bootPos] && snowPos+i < n; i++){
        if(f[snowPos + i] <= s[bootPos]){
            ret = min(ret, rec(snowPos+i, bootPos));
        }
    }
    return ret;
}
int main()
{
    freopen("snowboots.in", "r", stdin);
    freopen("snowboots.out", "w", stdout);
    scanf("%d %d", &n, &b);
    for(int i = 0; i<n; i++)
        scanf("%d", &f[i]);
    for(int i = 0; i<b; i++){
        scanf("%d %d", &s[i], &d[i]);
    }
    memset(dp, -1, sizeof dp);
    printf("%d\n", rec(0, 0));

    return 0;
}

Это мое решение этой проблемы (на C ++). Это просто рекурсия. Как говорит проблема,

• вы можете изменить загрузку, или
• вы можете сделать прыжок при текущей загрузке.

Запоминание выполняется двумерным массивом dp [] [].

Да, вы можете спасти ваше решение, добавив дополнительный for -кольцо.

Что вам нужно сделать, так это то, что если вы обнаружите, что ваша предыдущая пара ботинок может привести вас к плитке, которая слишком глубоко в снегу для вашей следующей пары, то вам нужно попытаться «вернуться» к последней плитке. это не слишком глубоко. В итоге получается решение в худшем случае O ( N · B ) времени и O (1) дополнительного пространства. [ 1161]

Может быть не очевидно, почему можно возвращаться к этой плитке - в конце концов, только потому, что вы можете достичь данной плитки, это не обязательно означает, что вы смогли добраться до всех плиток до нее - поэтому позвольте мне объясните немного, почему это нормально хорошо.

Пусть maxReachableTileNum будет номером (от 1 до N ) последней плитки, которой вы смогли достичь с вашими предыдущими ботинками, и пусть lastTileNumThatsNotTooDeep будет числом (от 1 до [ 1130] N ) последней плитки на или перед maxReachableTileNum, которая не слишком покрыта снегом для вашей следующей пары. (Мы знаем, что есть такая плитка, потому что плитка # 1 вообще не имеет снега, поэтому, если ничего другого, мы не знаем, что мы можем вернуться к самому началу.) Теперь, так как мы смогли получить до maxReachableTileNum, затем некоторая предыдущая загрузка должна была либо наступить на lastTileNumThatsNotTooDeep (в этом случае нет проблем, она достижима), либо пропустить его до некоторой более поздней плитки (до или после maxReachableTileNum) , Но эта более поздняя плитка должна быть глубже, чем lastTileNumThatsNotTooDeep (потому что эта более поздняя плитка больше, чем с _{currentBootNum} , что, по крайней мере, не меньше глубины lastTileNumThatsNotTooDeep ), что означает, что ботинок, который пропустил lastTileNumThatsNotTooDeep, безусловно, мог бы наступить на lastTileNumThatsNotTooDeep вместо этого: это означало бы сделать более короткий шаг (ОК) на плитку с менее глубоким покрытием (ОК ) чем то, что он на самом деле сделал. Так или иначе, мы знаем, что lastTileNumThatsNotTooDeep было достижимо. Поэтому мы можем попытаться вернуться к lastTileNumThatsNotTooDeep. (Примечание: приведенный ниже код использует имя reachableTileNum вместо lastTileNumThatsNotTooDeep, потому что он продолжает использовать переменную reachableTileNum для поиска вперед, чтобы найти достижимые тайлы.)

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