题解 P1215 【[USACO1.4]母亲的牛奶 Mother's Milk】

zhanghanbin · 2019-08-20 17:24:57 · 题解

本大菜鸡最喜欢使用 \LaTeX

目录：

这题到底是什么意思——理解题目
深搜怎么搜——构造递归函数
这题的坑好像比较弱——填坑
哇，竟然要输出所有的可能——答案存储与回溯
~~代码亮相^o^~~ cg:什么意思
提醒，找到链接的就在评论里留个言吧 ; - )

1. 题目大意

有三个桶，容量分别为 A, B, C 。这三个桶中 A, B 是空的，可以倒来倒去，最后问 A 桶为空的时候，C 桶中牛奶剩余量的种数。

\text{得出结论，本题需\color{red}暴力}

2. 暴力方法

不难发现，这一道题的搜索方向就是倒牛奶的方法：

\color{DarkOrchid}{1.A \Rightarrow B}

\color{DarkOrchid}{1.A \Rightarrow C}

\color{DarkOrchid}{1.B \Rightarrow A}$ $\color{red}{\textbf{\small{注意，这里的牛奶是可以重复倒的，}}} $ $\color{green}{\text{\tiny(是个梗(KEN),会处理)}}

\color{DarkOrchid}{1.B \Rightarrow C}

\color{DarkOrchid}{1.C \Rightarrow A}

\color{DarkOrchid}{1.C \Rightarrow B}

void dfs (int a, int b, int c) {
    if (c >= (A - a)) dfs(A, b, c - (A - a));
    else dfs(c + a, b, 0);

    //后面的事，先不管
}

在这里，需要分为两种情况判断，第一种是被倒的桶满了，装不下了，也就是c >= (A - a)。另一种是不够倒了，那就是c < (A - a)，其中A - a是 A 桶还能装的数量。

3. 填坑

这道题坑点在，你的 vis 数组，也就是记录情况的数组是三维的，但是这个三维数组的意义是记录 A, B, C 三个桶的状态，所以 dfs 函数的模型大概是这样：

void dfs (int a, int b, int c) {
    if (vis[a][b][c] == 1) return;
    else vis[a][b][c] = 1;

    if (c >= (A - a)) dfs(A, b, c - (A - a));
    else dfs(c + a, b, 0);

    //此处有省略大量重复内容，会在最后给出。
    //后面的事，先不管
}

4. 回溯与记录

答案是被暴力出来了，但是如何存储记录呢？

所以，这你就可以来一点 桶排序 然而其实排序是附赠的，我们需要的就只是一个统计功能。

我们新开一个数组 rec[i]。

于是就有了一段显而易见的代码：

if (a == 0 && rec[c] == 0) rec[c] = 1;

5. 最后

接下来就是最激动人心的时刻了，但是不是代码。

cg：cao，我看了这么久的题解，最后竟然不是代码！ zhb：别急，这可真的不是“最后”。
cg：emmmmmm。

那就是输出，输出自然就很简单，读入3个数 A, B, C 先按题目要求调用 dfs 函数： dfs(0, 0, C);

然后查找一下rec数组，

for (int i = 0; i <= 21; i++) {
    if (rec[i]) cout << i << ' ';
}

就大功告成了！

6. 代码

就是这样子啦：

cg：代码呢！？
zhb：为净化洛谷社区环境，决定不上代码
cg：你竟然骗我看到完，我现在就给你踩，亏我还给你评论！
zhb：别冲动呀！

\color{gray}{~~~~~~~~~~~~~~~~~~~~~~~~~~~}

\color{gray}{~~~~~~~~~~~~~~~~~~~~~~~~~~~}

\color{gray}{~~~~~~~~~~~~~~~~~~~~~~~~~~~}

\color{gray}{~~~~~~~~~~~~~~~~~~~~~~~~~~~}

\color{gray}{~~~~~~~~~~~~~~~~~~~~~~~~~~~}

\color{gray}{~~~~~~~~~~~~~~~~~~~~~~~~~~~}

咕咕，还没完呢！

6. 代码

zhb：像我这么好心的人，是不会不给代码的，所以还是
cg：远离代码抄袭犯罪，共建美好luogu！顶！

#include <iostream>

using namespace std;

int A, B, C;
int vis[22][22][22];
int rec[22];

void dfs(int a, int b, int c) {
    if (vis[a][b][c] == 1) return;
    else vis[a][b][c] = 1;

    if (a == 0 && rec[c] == 0) rec[c] = 1;

    if (c >= (A - a)) dfs(A, b, c - (A - a));
    else dfs(c + a, b, 0);

    if (c >= (B - b)) dfs(a, B, c - (B - b));
    else dfs(a, c + b, 0);

    if (b >= (A - a)) dfs(A, b - (A - a), c);
    else dfs(b + a, 0, c);

    if (b >= (C - c)) dfs(a, b - (C - c), C);
    else dfs(a, 0, b + c);

    if (a >= (C - c)) dfs(a - (C - c), b, C);
    else dfs(0, b, a + c);

    if (a >= (B - b)) dfs(a - (B - b), B, c);
    else dfs(0, a + b, c);
}

int main(int argc, char *argv[]) {
    cin >> A >> B >> C;
    dfs(0, 0, C);

    for (int i = 0; i <= 21; i++) {
        if (rec[i]) cout << i << ' ';
    }

    return 0;
}

注：由于在文章中已经详细阐述，所以不再提共注释！