C++# USACO14 母亲的牛奶 Mothers Milk## 题目描述农民约翰有三个容量分别是 $abc$ 升的桶。 最初$ab$ 桶都是空的而 $c$ 桶是装满牛奶的。有时农民把牛奶从一个桶倒到另一个桶中直到被灌桶装满或原桶空了。 当然每一次灌注都是完全的。由于节约牛奶不会有丢失。写一个程序去帮助农民找出当 $a$ 桶是空的时候$c$ 桶中牛奶所剩量的所有可能性。## 输入格式单独的一

分析

这是一个经典的深度优先搜索（DFS）问题。

我们可以将农民的操作看作是一个状态转移的过程。每个状态都由三个桶的当前牛奶量组成。我们可以用一个三维数组 visited[a+1][b+1][c+1] 来标记每个状态是否已经访问过。

我们可以从初始状态 (0, 0, c) 开始搜索，其中 c 是 c 桶中的牛奶量。然后，我们根据以下规则进行状态转移：

如果 a 桶中的牛奶量大于等于 b-a，我们可以将 b 桶倒满，并将 a 桶中的牛奶量减少 b-a。即 (a-(b-a), b, c)。
如果 a 桶中的牛奶量小于 b-a，我们可以将 b 桶中的牛奶量加上 a 桶中的牛奶量，并将 a 桶置空。即 (0, a+b, c)。
如果 a 桶中的牛奶量大于等于 c-a，我们可以将 c 桶倒满，并将 a 桶中的牛奶量减少 c-a。即 (a-(c-a), b, c-a)。
如果 a 桶中的牛奶量小于 c-a，我们可以将 a 桶中的牛奶量加上 a 桶中的牛奶量，并将 a 桶置空。即 (0, b, a+b)。
如果 b 桶中的牛奶量大于等于 a-b，我们可以将 a 桶倒满，并将 b 桶中的牛奶量减少 a-b。即 (b-(a-b), a, c)。
如果 b 桶中的牛奶量小于 a-b，我们可以将 a 桶中的牛奶量加上 b 桶中的牛奶量，并将 b 桶置空。即 (a+b, 0, c)。

我们可以使用递归函数来实现深度优先搜索，每次搜索时都尝试进行以上六种状态转移。当 a 桶为空时，将 c 桶中的牛奶量加入结果数组中。

算法

读取输入的 a, b, c。
初始化 visited 数组，并将所有元素都置为 false。
初始化结果数组 result。
调用深度优先搜索函数 dfs(0, 0, c)。
对结果数组进行排序。
输出结果数组。

复杂度分析

每个状态转移都有六种可能性，所以总的状态数为 $6^N$，其中 $N$ 是状态的最大深度，即 c 桶中的牛奶量。在本题中，$N$ 的最大值为 c，所以时间复杂度为 $O(6^c)$。由于 $c$ 的范围是 $1$ 到 $20$，因此算法的时间复杂度是可以接受的。

实现

下面是C++的实现代码：

#include <iostream>
#include <algorithm>
using namespace std;

bool visited[21][21][21]; // 用于标记状态是否已经访问过
int a, b, c; // 三个桶的容量
int result[21]; // 存储结果

void dfs(int x, int y, int z) {
    if (visited[x][y][z]) { // 如果当前状态已经访问过，则直接返回
        return;
    }
    visited[x][y][z] = true; // 标记当前状态为已访问

    if (x == 0) { // 如果a桶中的牛奶量为0，则将c桶中的牛奶量添加到结果数组中
        result[z] = 1;
    }

    // 六种状态转移
    dfs(max(0, x - (b - y)), min(b, x + y), z); // (a-(b-a), b, c)
    dfs(max(0, x - (c - z)), y, min(c, x + z)); // (a-(c-a), b, c-a)
    dfs(min(a, x + y), max(0, y - (a - x)), z); // (b-(a-b), a, c)
    dfs(x, max(0, y - (c - z)), min(c, y + z)); // (a, b-(c-a), c-a)
    dfs(min(a, x + z), y, max(0, z - (a - x))); // (b, a, c-(a-b))
    dfs(x, min(b, y + z), max(0, z - (b - y))); // (a, b, c-(b-a))
}

int main() {
    cin >> a >> b >> c;

    dfs(0, 0, c);

    sort(result, result + 21); // 对结果数组进行排序

    for (int i = 0; i < 21; i++) {
        if (result[i] != 0) {
            cout << result[i] << " ";
        }
    }
    cout << endl;

    return 0;
}

总结

本题是一个经典的深度优先搜索（DFS）问题，通过不断的状态转移，找出满足条件的结果。在实际编程中，我们可以使用递归函数来实现DFS，并使用一个三维数组来记录已经访问过的状态，以避免重复计算