随手练——USACO 1.44 母亲的牛奶

P1215 [USACO1.4]母亲的牛奶 Mother's Milk

---

洛谷 P1215：https://www.luogu.org/problemnew/show/P1215

解题思想：DFS

大一校内编程比赛的题目了，当时毛都没看懂，现在再拿出来，不能说小意思吧，那样说好像太狂了，中等意思吧

一个杯子往另一个杯子里倒，分两种情况。

假设A杯，B杯（大小关系是不影响的，反过来一样）：

需要注意的就是，添加一个flag数组，标记已经做过的状态。

#include <iostream>

#include <set>

using namespace std;

set<int>s;

bool flag[][][];

int A, B, C;

int min(int a,int b) {

    return a < b ? a : b;

}

void DFS(int a,int b,int c) {

    if (flag[a][b][c])return;

    else

        flag[a][b][c] = true;

    if (a > A || b > B || c > C) {

        return;

    }

    if (a == ) {

        s.insert(c);

    }

    if (a > ) {

        //a->b

        DFS(a - min(B - b, a), b + min(B - b, a), c);

        //a->c

        DFS(a - min(C - c, a), b, c + min(C - c, a));

    }

    if (b > ) {

        //b->a

        DFS(a + min(b, A - a), b - min(b, A - a), c);

        //b->c

        (a, b - min(b, C - c), c + min(C - c, b));

    }

    if (c > ) {

        //c->a

        DFS(a + min(A - a, c), b, c - min(A - a, c));

        //c->b

        DFS(a, b + min(B - b, c), c - min(c, B - b));

    }

}

int main() {

    int i = ;

     cin >> A >> B >> C;

    DFS(, , C);

    set<int>::iterator it = s.begin();

    while (it != s.end()) {

        if ((i++) == s.size() - )break;

        cout << *it << " ";

        it++;

    }

    cout << *it << endl;

    return ;

}