题解 P3139 【[USACO16FEB]牛奶桶Milk Pails】

· · 题解

可以不用dp，dfs和bfs也是可以的；

首先 dfs：f[i][j]表示两桶量分别为i，j是否出现过，就可以剪枝；

附上dfs代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
 using namespace std;
int x,y,k,m;
bool f[105][105];
int ans=1e9;
void dfs(int xn,int yn,int kn)
{
    if ((f[xn][yn]==1)||(kn-1>k)) return;
    f[xn][yn]=1;
    ans=min(ans,abs(m-xn-yn));
    dfs(x,yn,kn+1);
    dfs(xn,y,kn+1);
    dfs(0,yn,kn+1);
    dfs(xn,0,kn+1);
    if(x-xn<=yn) dfs(x,yn-(x-xn),kn+1);
    else dfs(xn+yn,0,kn+1);
    if(y-yn<=xn) dfs(xn-(y-yn),y,kn+1);
    else dfs(0,xn+yn,kn+1);
    f[xn][yn]=0;
    return;
}
int main() 
{   
    scanf("%d%d%d%d",&x,&y,&k,&m);
    dfs(0,0,1);
    cout<<ans<<endl;
    return 0;
}

其次bfs：思路差不多；c[i][j]表示得到第一个杯子i升，第二个杯子j升，最小的操作次数，也就是在搜索树中层数 初始(0,0)入队，两个杯子中的容量都是0

取出队列首元素：(p,q)

考虑子结点，任意一个杯子倒空，任意一个杯子装满，从一个杯子倒入另一个杯子

bfs代码就不贴了（其实我懒）