倒水问题 POJ 1606 自己的解法好慢的说。

#include<iostream>
using namespace std;
//============================================
int A,B,res,t;
int vis[1000][1000];
int path[1000];
int minpath[1000];
int minstep=10000;
char p[6][20]={"fill A","fill B","empty A","empty B","pour A B","pour B A"};
bool Search(int a,int b,int order)
{
if(vis[a][b]==1)return 0;
if(b==res)
{
if(order<minstep)
{
memcpy(&minpath,&path,sizeof(path));
}
return 1;
}
     vis[a][b]=1;
   if(a<A)
{
path[order]=1;
   if(Search(A,b,order+1))//==fill A
{
   return 1;
}
  }
if(b<B)
{
path[order]=2;
   if(Search(a,B,order+1))//==fill B
{
   return 1;
}
}
if(a>0&&a<=A)
{
path[order]=3;
if(Search(0,b,order+1))//==empty A
{
return 1;
}
}
if(b>0&&b<=B)
{
path[order]=4;
if(Search(a,0,order+1))//==empty B
{
return 1;
}
}
if(a>0&&a<=A&&b<B)
{
path[order]=5;
       if(Search(max(0,a+b-B),min(a+b,B),order+1))//==pour A into B
{
   return 1;
}
}
if(b>0&&b<=B&&a<A)
{
path[order]=6;
if(Search(min(a+b,A),max(0,a+b-A),order+1))//==pour B into A
{
   return 1;
}
vis[a][b]=0;
return 0;
}
}
int main()
{
//freopen("E:/ACM/in.txt", "r", stdin);
while(cin>>A>>B>>res)
{
memset(vis,0,sizeof(vis));
memset(path,0,sizeof(path));
memset(minpath,0,sizeof(minpath));
if(Search(0,0,1))
{
int i=1,m;
while(minpath[i]!=0)
{
i++;
}
m=i;
       for(i=1;i<m;++i)
{
cout<<p[minpath[i]-1]<<endl;
}
cout<<"success"<<endl;
}
}
return 0;
}

posted @ 2011-09-15 20:24 四也 阅读(215) | 评论 (0)编辑 收藏

Arithmetic Progressions 剪枝做的不好,最后险过

/*
ID: skylove3
PROG: ariprog
LANG: C++
*/
#include<iostream>
#include<algorithm>
#include<fstream>
#include<cstring>
using namespace std;
//=========================================
struct Point//记录符合条件的坐标
{
int x;
int y;
};
Point s[130000];//数组开小了,剪枝
int cmp( const void *a , const void *b )//结构体排序,妙
{    
struct Point *c = (Point *)a;
     struct Point *d = (Point *)b;
     if(c->y != d->y) 
return c->y - d->y;
     else return c->x - d->x;
}
Point q;
int length,M;
int p[130000];
int mark[130000];
int k=0;
void Search(const int &a,const int &b,const int &n)
{
if(n==length)//出口
{
q.x=a;
q.y=b;
s[k]=q;
k++;
return ;
}
else
{
if(mark[a+n*b]==1)//标记
{
Search(a,b,n+1);
}
else
{
return;
}
}
}
int main()
{
ofstream fout("ariprog.out");
ifstream fin("ariprog.in");
fin>>length>>M;
    memset(p,0,sizeof(p));
int t=1;
for(int i=0;i<=M;++i)
{
for(int j=0;j<=M;++j)
{  
p[t]=i*i+j*j;
mark[p[t]]=1;
t++;
}
}
for(int i=1;i<=(M+1)*(M+1);++i)
{
for(int j=1;j<=(M+1)*(M+1)/2;++j)
{
if(i+(length-1)*j>2*(M+1)*(M+1))//剪枝,此处在主程序中
{
break;
}
   Search(p[i],j,1);
}
}
int flag=0;
int sum=0;
for(int i=0;i<1000;i++)
{
if(s[i].x==0&&s[i].y==0)
{   
sum=i+1;
break;
}
}
for(int i=0;i<sum;++i)
{
if(s[i].x!=0||s[i].y!=0)
{
flag=1;
break;
}
}
if(flag==0)
{
fout<<"NONE"<<endl;
return 0;
}
qsort(s,sum,sizeof(s[0]),cmp);
for(int i=0;i<sum;++i)
{
if((s[i].x==0&&s[i].y==0)||(s[i].x==s[i-1].x&&s[i].y==s[i-1].y))
{
continue;
}
fout<<s[i].x<<" "<<s[i].y<<endl;
}
}

posted @ 2011-09-13 21:45 四也 阅读(97) | 评论 (0)编辑 收藏

我会走下去。ACM

开始ACM了,从8月30号开始集训。我真是弱爆了。。什么都不会。。。不过,我喜欢ACM,我希望变得更强。我会一直走下去。

posted @ 2011-09-10 09:12 四也 阅读(134) | 评论 (0)编辑 收藏

仅列出标题
共2页: 1 2 
<2024年4月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜