计蒜客——无脑博士的试管们

题目：

无脑博士有三个容量分别是 A,B,C 升的试管，A,B,C 分别是三个从 1 到 20 的整数，最初，A和 B 试管都是空的，而 C 试管是装满硫酸铜溶液的。有时，无脑博士把硫酸铜溶液从一个试管倒到另一个试管中，直到被灌试管装满或原试管空了。当然每一次灌注都是完全的。由于无脑博士天天这么折腾，早已熟练，溶液在倒的过程中不会有丢失。

写一个程序去帮助无脑博士找出当 A 试管是空的时候，C 试管中硫酸铜溶液所剩量的所有可能性。

输入格式

输入包括一行，为空格分隔开的三个数，分别为整数 A,B,C。

输出格式

输出包括一行，升序地列出当 A试管是空的时候，C试管溶液所剩量的所有可能性。

样例输入

2 5 10

样例输出

5 6 7 8 9 10

类型：DFS，动态规划

代码：

#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;

int A,B,C;
//res[a][b] 存储A B中液体为a b的情况是否遍历过
int res[21][21];

//深搜 回溯
//参数为A B C 试管的液体总量
void backtrace(int a,int b,int c)
{
    res[a][b] = 1;
    int a0 = a, b0 = b, c0 = c;
    if(a < A){ //A未满
        if(b > 0){ //B -> A
            if(b >= A-a){ // A倒满
                b = b-A+a;
                a = A;
            }
            else{ //B倒空
                a += b;
                b = 0;
            }
            if(res[a][b] == 0)backtrace(a,b,c);
            a = a0;
            b = b0;
        }
        if(c > 0){ //C -> A
            if(c >= A-a){ // A倒满
                c = c-A+a;
                a = A;
            }
            else{ //C倒空
                a += c;
                c = 0;
            }
            if(res[a][b] == 0)backtrace(a,b,c);
            a = a0;
            c = c0;
        }
    }
    if(b < B){ //B未满
        if(a > 0){ //A -> B
            if(a >= B-b){ // B倒满
                a = a-B+b;
                b = B;
            }
            else{ //A倒空
                b += a;
                a = 0;
            }
            if(res[a][b] == 0)backtrace(a,b,c);
            a = a0;
            b = b0;
        }
        if(c > 0){ //C -> B
            if(c >= B-b){ // B倒满
                c = c-B+b;
                b = B;
            }
            else{ //C倒空
                b += c;
                c = 0;
            }
            if(res[a][b] == 0)backtrace(a,b,c);
            b = b0;
            c = c0;
        }
    }
    if(c < C){ //C未满
        if(a > 0){ //A -> C
            if(a >= C-c){ // C倒满
                a = a-C+c;
                c = C;
            }
            else{ //A倒空
                c += a;
                a = 0;
            }
            if(res[a][b] == 0)backtrace(a,b,c);
            a = a0;
            c = c0;
        }
        if(b > 0){ //B -> C
            if(b >= C-c){ // C倒满
                b = b-C+c;
                c = C;
            }
            else{ //B倒空
                c += b;
                b = 0;
            }
            if(res[a][b] == 0)backtrace(a,b,c);
            b = b0;
            c = c0;
        }
    }


}

int main()
{
    scanf("%d %d %d",&A,&B,&C);
    backtrace(0,0,C);
    /*for(int i=0; i<21; i++){
        for(int j=0; j<21; j++){
            cout << res[i][j] << " ";
        }
        cout << endl;
    }*/

    int k=0;
    for(int i=B; i >= 0; i--){
        //cout << res[0][i] << " ";
        if(res[0][i] == 1){
            if(k==0){
                cout << C-i;
                k=1;
            }
            else{
                cout << " " << C-i ;
            }
        }
    }
    cout << endl;

    return 0;
}

 PS: 注意输出格式，最后没有空格.....