自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:07:19，当前版本为作者最后更新于2019-01-02 19:45:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

用数组存储每个桶当前所在的位置（$1$ 或 $2$），模拟每一天会发生的情况。

用一个 $\mathrm{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;
}

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