1 条题解

  • 0
    @ 2026-5-19 1:05:36

    大致思路:dfs +\mathrm{dfs}\ + 模拟。

    用数组存储每个桶当前所在的位置(1122),模拟每一天会发生的情况。

    用一个 vector\mathrm{vector} 存答案(最后一天第一个奶罐里的牛奶量),最后输出这个 vector\mathrm{vector} 的大小就行了。


    实现细节见代码

    #include<bits/stdc++.h>
    using namespace std;
    vector <int> ans;//最后一天第一个奶罐里的牛奶量
    int pd[22],t[22];//pd数组存储位置,t数组存储容积
    void dfs(int w,int m)//w是星期几,m是第一个奶罐中的牛奶量
    {
    	if(w/6){//如果到了星期六
    		for(int x=0;x<ans.size();x++)//遍历整个ans数组
    			if(m==ans[x])return;//如果重复,就返回
    		ans.push_back(m);//否则将这一种情况压入答案
    		return;
    	}
    	for(int x=1;x<=20;x++){
    		if(w%2==0&&pd[x]==1){//如果星期是双数(也就是从第一个挤奶棚前往第二个挤奶棚),并且这个桶在第一个挤奶棚
    			pd[x]=2;//就把这个桶装满带到第二个挤奶棚
    			dfs(w+1,m-t[x]);//dfs下一天,因为带出第一个奶棚,所以是 "-"
    			pd[x]=1;//记得要回到原来的状态!
    		}
    		if(w%2==1&&pd[x]==2){//如果星期是单数,并且这个桶在第二个挤奶棚
    			pd[x]=1;//装满,带回第一个挤奶棚
    			dfs(w+1,m+t[x]);//dfs下一天,带回第一个奶棚,用 "+"
    			pd[x]=2;//回溯
    		}
    	}
    }
    int main()
    {
    	for(int x=1;x<=20;x++)cin>>t[x],pd[x]=x<11?1:2;//输入,如果是后10个就在第二个奶棚
    	dfs(2,1000);//从星期二开始,第一个奶罐里有1000牛奶
    	cout<<ans.size();//输出答案总数
    	return 0;
    }
    

    Upd:2019.12.11:\mathrm{Upd:2019.12.11:} 添加 Latex\mathrm{Latex},美化文章。

    • 1

    信息

    ID
    6777
    时间
    1000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    37
    已通过
    8
    上传者