usaco_milk3.cpp

usaco自己做的1到5章的代码

/*
ID:wangyuc2
PROG:milk3
LANG:C++
*/
#include <iostream>
#include <fstream>
using namespace std;
int total=0,a,b,c,aa,bb,cc,data[1000]={0};
int atem[1000],btem[1000],ctem[1000],amax=0,bmax=0,cmax=0;
bool check[21][21][21]={false};
bool nothave();
void dfssearch(int ii);
void work(int jj);
void quicksort(int data1[],int first,int last);
int main()
{
    ifstream fin ("milk3.in");
    ofstream fout ("milk3.out");
    
    int i,j,k;
    fin >> a >> b >> c;
    aa=0;
    bb=0;
    cc=c;
    check[0][0][c]=true;
    amax++;
    bmax++;
    cmax++;
    atem[amax]=0;
    btem[bmax]=0;
    ctem[cmax]=c;
    dfssearch(3);
    for (i=0;i<=20;i++) for (j=0;j<=20;j++) for (k=0;k<=20;k++) check[i][j][k]=false;
    check[0][0][c]=true;
    amax=1;
    bmax=1;
    cmax=1;
    atem[amax]=0;
    btem[bmax]=0;
    ctem[cmax]=c;
    dfssearch(5);
    quicksort(data,1,total);
    for (i=1;i<=total-1;i++) fout << data[i] << ' ';
    fout << data[total] << endl;
    fin.close();
    fout.close();
    return 0;
}
void dfssearch(int ii)
{
    int iii;
    if (aa==0 && nothave())
    {
        total++;
        data[total]=cc;
    }
    work(ii);
    amax++;
    bmax++;
    cmax++;
    atem[amax]=aa;
    btem[bmax]=bb;
    ctem[cmax]=cc;
    if (check[aa][bb][cc]) return;
    check[aa][bb][cc]=true;
    for (iii=1;iii<=6;iii++)
    {
        dfssearch(iii);
        aa=atem[amax-1];
        bb=btem[bmax-1];
        cc=ctem[cmax-1];
        amax--;
        bmax--;
        cmax--;
    }
}
void work(int jj)
{
    if (jj==1)
    {
        if (aa>b-bb)
        {
            aa=aa-b+bb;
            bb=b;
        }
        else
        {
            bb=bb+aa;
            aa=0;
        }
    }
    else if (jj==2)
    {
        if (bb>c-cc)
        {
            bb=bb-c+cc;
            cc=c;
        }
        else
        {
            cc=cc+bb;
            bb=0;
        }
    }
    else if (jj==3)
    {
        if (cc>a-aa)
        {
            cc=cc-a+aa;
            aa=a;
        }
        else
        {
            aa=aa+cc;
            cc=0;
        }
    }
    else if (jj==4)
    {
        if (aa>c-cc)
        {
            aa=aa-c+cc;
            cc=c;
        }
        else
        {
            cc=cc+aa;
            aa=0;
        }
    }
    else if (jj==5)
    {
        if (cc>b-bb)
        {
            cc=cc-b+bb;
            bb=b;
        }
        else
        {
            bb=bb+cc;
            cc=0;
        }
    }
    else
    {
        if (bb>a-aa)
        {
            bb=bb-a+aa;
            aa=a;
        }
        else
        {
            aa=aa+bb;
            bb=0;
        }
    }
}
bool nothave()
{
    int jjj;
    for (jjj=1;jjj<=total;jjj++) if (data[jjj]==cc) return false;
    return true;
}
void quicksort(int data1[],int first,int last)
{
    int ii=first;
    int jj=last;
    int xx=data1[ii];
    while (ii<jj)
    {
        while (data1[jj]>xx && ii<jj) jj=jj-1;
        if (ii<jj)
        {
            data1[ii]=data1[jj];
            ii=ii+1;
        }
        while (data1[ii]<xx && ii<jj) ii=ii+1;
        if (ii<jj)
        {
            data1[jj]=data1[ii];
            jj=jj-1;
        }
    }
    data1[ii]=xx;
    if (first<ii-1) quicksort(data1,first,ii-1);
    if (ii+1<last) quicksort(data1,ii+1,last);
}