当前位置：首页 > news >正文

【递归完全搜索】USACO Bronze 2018 December - 往返搬运Back and Forth

news 2025/8/9 12:18:17

题目描述

农夫约翰（Farmer John）有两个挤奶棚，每个棚中都有一个巨大的储奶罐，以及一个储物柜，里面各自装有 $10$ 个不同容量的水桶。他喜欢通过在两个棚之间运奶来锻炼身体。

在 星期一，农夫约翰分别在两个棚的储奶罐中各装入 1000 加仑的牛奶。

接下来的四天，他每天会进行如下操作：

星期二：从第一个棚中拿出一个水桶，装满牛奶后带到第二个棚，把牛奶倒入第二个棚的储奶罐中，然后把水桶留在第二个棚。
星期三：从第二个棚中拿一个水桶（可能是星期二留下的那个），装满牛奶后带到第一个棚，把牛奶倒入第一个棚的储奶罐中，然后把水桶留在第一个棚。
星期四：从第一个棚中拿一个水桶（可能是前一天带回来的那个），装满牛奶后带到第二个棚，把牛奶倒入第二个棚的储奶罐中，然后把水桶留在第二个棚。
星期五：从第二个棚中拿一个水桶（可能是前几天带过去的某个），装满牛奶后带到第一个棚，把牛奶倒入第一个棚的储奶罐中，然后把水桶留在第一个棚。

五天过后，农夫约翰测量了 第一个棚储奶罐中剩余的牛奶量。他想知道，这个值有多少种不同的可能？

输入格式

第 $1$ 行： $10$ 个整数，表示第一个棚中水桶的容量。

第 $2$ 行： $10$ 个整数，表示第二个棚中水桶的容量。

所有水桶的容量范围均为 $1$ 到 $100$ 。

输出格式

输出一个整数，表示最终第一个棚储奶罐中 可能出现的不同牛奶量的个数。

样例输入

1 1 1 1 1 1 1 1 1 2
5 5 5 5 5 5 5 5 5 5

样例输出

样例解释

最后，第一个棚的储奶罐可能出现如下 5 种牛奶量：

1000：例如每次都用同一个桶来回搬运（1→5→1→5），刚好收支相抵。
1003：星期二用 2 加仑的桶送出，星期三用 5 加仑的桶送回，星期四送出 1 加仑桶，星期五送回 1 加仑桶，净增加 3。
1004：星期二送出 1，加回 5，再送 1，再加回 1，净增加 4。
1007：送出 1，加回 5，送出 2，加回 5，净增加 7。
1008：送出 1，加回 5，送出 1，加回 5，净增加 8。

提交链接

https://usaco.org/index.php?page=viewproblem2&cpid=857

思路分析

🧠 问题建模思路

🎯 目标

我们要确定在经过 $4$ 天搬运过程（周二到周五）之后，第一个棚里的储奶罐可能剩下多少种不同的牛奶量。

🧩 问题简化与观察

这不是一个模拟题，而是一个穷举所有可能状态的组合问题。题目中的搬运方式遵循以下规律：

每天搬运一次，共 $4$ 天。
每次搬运从当前棚中选一个桶，装满后带到另一个棚，将奶倒入后把桶留在那里。
搬运顺序固定：
- 周二：A → B
- 周三：B → A
- 周四：A → B
- 周五：B → A

🧠 状态空间思考

这个问题的核心是 —— 在 $4$ 步桶的移动中，不同的选择路径最终会导致不同的牛奶分布，尤其是第一个桶中的最终值。但每一步的决策都取决于当前棚中有哪些桶，所以状态的变化不仅包括奶量的变化，还包括桶的分布变化。

因此每一个状态应该包括：

当前是第几天（day）
棚 A 的牛奶量（v_a）
棚 B 的牛奶量（v_b）
棚 A 当前的桶（a）
棚 B 当前的桶（b）

每次我们从当前棚中拿一个桶，更新两个棚的桶列表，并转移相应的牛奶。

✅ 解题策略：DFS（深度优先搜索）

我们要枚举所有可能的“桶选择顺序”，每次从当前棚中任选一个桶进行搬运，更新状态后递归下一天。

❓ 为什么选择 DFS？

每一步最多有 $10$ 个桶可选
只递归 $4$ 层（ $4$ 天）
状态数量最多是 $10^4$ 左右，可以接受

我们不关心路径本身，只关心最后的结果（第一棚的奶量），所以可以用一个 set 把所有最终结果记录下来。

🔄 状态转移逻辑

在 dfs(day, v_a, a, v_b, b) 中，我们表示当前是第 day 天，棚 A 有 v_a 单位奶，棚 B 有 v_b 单位奶。

每次递归时：

当前是第 day 天，从当前棚（a）中枚举每一个桶：
- 将这个桶从 a 移除，加入到 b
- 将这个桶的容量对应的牛奶从 v_a 减去，加到 v_b 上
- 然后递归下一天
- 注意：此时 A 和 B 的角色互换（搬运是双向交替的）

我们用递归完成这个过程，直到 day == 4，表示搬运完了 4 次，此时把 v_a 记录到结果集合中。

📦 终止条件

当 day == 4，表示已经进行了 4 次搬运，此时记录第一个桶的牛奶量。

由于使用的是 set<int>，它会自动去重，记录所有不同的结果。

参考代码

#include <bits/stdc++.h>
using namespace std;
set<int> s;// 周几  从a-->b
void dfs(int day, int v_a, vector<int> a, int v_b, vector<int> b)
{if (day == 4){s.insert(v_a);return;}for (int i = 0; i < a.size(); i++){vector<int> a1 = a;a1.erase(begin(a1) + i);vector<int> b1 = b;b1.push_back(a[i]);dfs(day + 1, v_b + a[i], b1, v_a - a[i], a1);}
}
int main()
{// freopen("backforth.in", "r", stdin);// freopen("backforth.out", "w", stdout);vector<int> a(10), b(10);for (auto &it : a)cin >> it;for (auto &it : b)cin >> it;dfs(0, 1000, a, 1000, b);cout << s.size();return 0;
}