首页 > 其他 > 详细

usaco Mother's Milk

时间:2015-08-28 19:22:25      阅读:285      评论:0      收藏:0      [点我收藏+]

给了三个木桶的容量,起始状态下C木桶装满,然后三个木桶相互倒牛奶,问当A木桶为空时的C木桶的牛奶体积的可能情况。

直接深度优先搜索,模拟三个木桶相互倒的情况

相互倒得情况本可以写的更简洁,但为了可阅读性我并没有这么干

不过这道题在本机上调试时,我曾将一个我认为无关紧要的地方写错,因为两个数组大小一样,所以在sizeof的括号中写了另外一个,结果却出不了正解。

有机会要好好查查memcyp函数的用法。

/*
ID: modengd1
PROG: milk3
LANG: C++
*/
#include <iostream>
#include <stdio.h>
#include <memory.h>
bool tag[21];
using namespace std;
bool vis[21][21][21];
int buc[3];
void slove(int L[3])
{
    int Lcopy[3];
    if(vis[L[0]][L[1]][L[2]])
        return ;
    vis[L[0]][L[1]][L[2]]=true;
    //如果A桶空了,则将C桶的数标记
    if(L[0]==0)
        tag[L[2]]=true;
    for(int i=0;i<3;i++)
    {
        for(int j=i+1;j<3;j++)
        {
            memcpy(Lcopy,L,sizeof(Lcopy));
            //i->j
            //j还未满,i未空
            if(buc[j]!=Lcopy[j]&&Lcopy[i]!=0)
            {
                //取j的剩余空间和i的剩余牛奶的最小值
                int change=min(Lcopy[i],buc[j]-Lcopy[j]);
                Lcopy[j]+=change;
                Lcopy[i]-=change;
                slove(Lcopy);
            }
            memcpy(Lcopy,L,sizeof(Lcopy));//此处我曾将sizeof括号中Lcopy写成L,但跑不对,主观觉着本应该不会影响的。
            //j->i
            //i还未满,j未空
            if(buc[i]!=Lcopy[i]&&Lcopy[j]!=0)
            {
                //取i的剩余空间和j的剩余牛奶的最小值
                int change=min(Lcopy[j],buc[i]-Lcopy[i]);
                Lcopy[i]+=change;
                Lcopy[j]-=change;
                slove(Lcopy);
            }
        }
    }
}
int main()
{
    freopen("milk3.in","r",stdin);
    freopen("milk3.out","w",stdout);
    int L[3];
    memset(vis,false,sizeof(vis));
    memset(tag,false,sizeof(tag));
    scanf("%d%d%d",&buc[0],&buc[1],&buc[2]);
    L[0]=L[1]=0;
    L[2]=buc[2];
    slove(L);
    bool isfrist=true;
    for(int i=0;i<=20;i++)
    {
        if(tag[i])
        {
             if(isfrist)
            {
                cout<<i;
                isfrist=false;
            }
            else
            {
                cout<<‘ ‘<<i;
            }
        }
    }
    cout<<endl;
    return 0;
}

  

usaco Mother's Milk

原文:http://www.cnblogs.com/modengdubai/p/4767066.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!