题目描述

递归型枚举  dfs(int w,int sum);表示第w天，第一个桶的牛奶数量为sum
递归边界为 当到星期六的时候，对第一个桶的牛奶数量进行统计，如果之前已经有了，不记录，如果没有，记录
递归 （1）如果为2，4表示将牛奶从第一个桶放入第二个桶  并且当前枚举的桶属于第一个罐的位置
(2)如果为3，5表示将牛奶从第二个桶放入第一个桶的  此时桶的位置在第二个桶
对于是否将桶留在当前位置

算法1

C++ 代码

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

vector<int> res;
int t[20],pd[20];//分别村每一个桶的大小，以及分别属于哪一个桶

void dfs(int w,int sum){
    if(w/6){//统计牛奶的数量
        for(int i=0;i<res.size();i++){
            if(res[i]==sum){
                return ;
            }
        }
        res.push_back(sum);
        return ;//统计完以后返回
    }
    //队第w天使用的桶进行枚举
    for(int i=1;i<=20;i++){
        if(w%2==0&&pd[i]==1){
            pd[i]=2;
            dfs(w+1,sum-t[i]);
            //恢复现场
            pd[i]=1;
        }
        if(w%2==1&&pd[i]==2){
            pd[i]=1;
            dfs(w+1,sum+t[i]);
            pd[i]=2;
        }
    }

}

int main(){
    for(int i=1;i<=20;i++){
        cin>>t[i];
        pd[i]= i>10? 2:1;
    }

    dfs(2,1000);

    cout<<res.size()<<endl;
    return 0;
}