题解 P5118 【[USACO18DEC]Back and Forth】

· · 题解

大致思路：\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;
}