【TImeGate】
https://www.luogu.org/problem/P5118
【解题思路】
dfs+模拟
【code】
具体思路见代码
1 #include<bits/stdc++.h>
2 using namespace std;
3 vector <int> ans;//最后一天第一个奶罐里的牛奶量
4 int pd[22],t[22];//pd数组存储位置，t数组存储容积
5 void dfs(int w,int m)//w是星期几，m是第一个奶罐中的牛奶量
6 {
7 if(w/6){//如果到了星期六
8 for(int x=0;x<ans.size();x++)//遍历整个ans数组
9 if(m==ans[x])return;//如果重复，就返回
10 ans.push_back(m);//否则将这一种情况压入答案
11 return;
12 }
13 for(int x=1;x<=20;x++){
14 if(w%2==0&&pd[x]==1){//如果星期是双数（也就是从第一个挤奶棚前往第二个挤奶棚），并且这个桶在第一个挤奶棚
15 pd[x]=2;//就把这个桶装满带到第二个挤奶棚
16 dfs(w+1,m-t[x]);//dfs下一天，因为带出第一个奶棚，所以是 "-"
17 pd[x]=1;//记得要回到原来的状态！
18 }
19 if(w%2==1&&pd[x]==2){//如果星期是单数，并且这个桶在第二个挤奶棚
20 pd[x]=1;//装满，带回第一个挤奶棚
21 dfs(w+1,m+t[x]);//dfs下一天，带回第一个奶棚，用 "+"
22 pd[x]=2;//回溯
23 }
24 }
25 }
26 int main()
27 {
28 for(int x=1;x<=20;x++)cin>>t[x],pd[x]=x<11?1:2;//输入，如果是后10个就在第二个奶棚
29 dfs(2,1000);//从星期二开始，第一个奶罐里有1000牛奶
30 cout<<ans.size();//输出答案总数
31 return 0;
32 }