java - USACO 2018 年 12 月铜牌返回错误输出

Question

2018 年 12 月的 USACO 铜牌问题，BackForth 问题:http://usaco.org/index.php?page=viewproblem2&cpid=857

我的代码:

import java.util.*;
import java.io.*;
public class backforth
{
    //  static int[] poss = new int[2000];
    static ArrayList<Integer> poss = new ArrayList<Integer>();
    public static void tuesday(int milk, ArrayList<Integer> one, ArrayList<Integer> two)
    {
        for(int i = 0; i < one.size(); i++)
        {
            int x = one.get(i);
//          ArrayList<Integer> twoNew = two; twoNew.add(x);
//          ArrayList<Integer> oneNew = one; oneNew.remove(i);
            two.add(x);
            one.remove(i);
            wednesday(milk - x, one, two);
        }
    }

    public static void wednesday(int milk, ArrayList<Integer> one, ArrayList<Integer> two)
    {
        for(int i = 0; i < two.size(); i++)
        {
            int x = two.get(i);
//          ArrayList<Integer> oneNew = one; oneNew.add(x);
//          ArrayList<Integer> twoNew = two; twoNew.remove(i);
            one.add(x);
            two.remove(i);
            thursday(milk + x, one, two);
        }
    }

    public static void thursday(int milk, ArrayList<Integer> one, ArrayList<Integer> two)
    {
        for(int i = 0; i < one.size(); i++)
        {
            int x = one.get(i);
//          ArrayList<Integer> twoNew = two; twoNew.add(x);
//          ArrayList<Integer> oneNew = one; oneNew.remove(i);
            two.add(x);
            one.remove(i);
            friday(milk - x, one, two);
        }
    }

    public static void friday(int milk, ArrayList<Integer> one, ArrayList<Integer> two)
    {
        for(int i = 0; i < two.size(); i++)
        {
            int x = two.get(i);
            int add = milk + x;
            if(!poss.contains(add))
                poss.add(add);
        }
    }

    public static void main(String[] hi) throws IOException
    {
        BufferedReader in = new BufferedReader(new FileReader("backforth.in"));
        PrintWriter out = new PrintWriter(new File("backforth.out"));
        StringTokenizer st;

        st = new StringTokenizer(in.readLine());
        ArrayList<Integer> B1 = new ArrayList<Integer>();
        ArrayList<Integer> B2 = new ArrayList<Integer>();

        for(int i = 0; i < 10; i++)
        {
            B1.add(Integer.parseInt(st.nextToken()));
        }

        st = new StringTokenizer(in.readLine());
        for(int i = 0; i < 10; i++)
        {
            B2.add(Integer.parseInt(st.nextToken()));
        }
        tuesday(1000, B1, B2);

        //for(int  i = 0; i < poss.size(); i++)
        //  System.out.println(poss.get(i) + " ");
        System.out.println(poss.size());
        in.close();out.close();
    }
}

输出应该是 5，但我得到的是 9。我不知道如何修改代码以获得正确的输出——我尝试了几种不同的方法，但我没有得到正确的输出。

我为谷仓 1 获得的可能牛奶产量:

1008 
1004 
1007 
1003 
1005 
1000 
1001 
996 
997 
9

但是，它应该是 1000, 1003, 1004, 1007, 1008。

Answer 1

您的方法非常正确，可以将其表述为 graph problem ;在给定的一天，您遍历谷仓中的每个桶并尝试搬运它，当唯一时存储星期五的最终结果。

但是，要使其正常工作，每次您从谷仓中提一个桶并递归到子状态时，您都需要“撤消”返回父状态时转移的牛奶。这样，当您尝试在下一次迭代中使用不同的存储桶时，您将拥有一个全新的工作状态，而不会受到之前递归模拟的污染。

考虑以下几行:

two.add(x);
one.remove(i);
wednesday(milk - x, one, two);

在执行的这一点上，状态已经永久损坏，这意味着原始状态的桶不再与其输入匹配，循环中的任何进一步计算都将不准确。

相反，尝试按如下方式恢复状态:

two.add(x);
one.remove(i);
wednesday(milk - x, one, two);
one.add(i, two.remove(two.size()-1)); // undo the milk transfer

使用这种方法，在调用 wednesday() 之后，牛奶量和桶恢复到其原始状态，并且测试其他桶的循环的 future 迭代将准确地做到这一点。

您还可以在修改这些数组之前复制它们，看起来您已经尝试过了。这是一个正确的想法，也能奏效，但与简单地撤消每个 Action 并始终只使用两个列表相比，它的性能要差一些。

此外，代码可以进行一些重组，这可能有助于了解您的程序状态、减少重复(潜在错误!)并简化重构。

没有理由为一周中的每一天设置不同的函数，因为每天都执行相同的过程，即递归地尝试将每个可用的桶运送到另一个 jar 中。您可以使用 day变量来表示当前日期，并在每次递归调用中递增它。如果您从第 0 天开始，你的递归基本情况是 day == 4 , 此时您可以记录最后的 milk该桶选择序列的金额。要确定 Farmer Brown 在给定的一天从哪个谷仓开始，您可以采用 day 的模数。或者在每次递归调用时交换源桶数组和目标桶数组，并找到一种方法来根据您所在的谷仓添加或减去牛奶量。

最后，if(!poss.contains(add))是一个线性过程，需要查看列表中的每个元素，并且会对结果计算造成巨大的性能影响。使用 HashSet存储唯一的可能结果。该集合的大小就是您的最终结果。