深搜
$O( < 6^k)$
将dfs里面用循环归纳好,然后用哈希表存储。
有没有感觉长得像bfs
AC code
#include<iostream>
#include<unordered_map>
#include<cstring>
using namespace std;
const int N=4001;
int b[3];
unordered_map<int,bool> st;
bool stc[N];
int get(int a,int b,int c) //获取哈希值(4001进制)
{
return a*N*N+b*N+c;
}
int res=0;
int dfs(int a[]) //深度搜索不同的水量
{
int t[3];
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(i==j) continue;
// i -> j
for(int k=0;k<3;k++) t[k]=a[k];
t[i]=max(0,a[i]-b[j]+a[j]),t[j]=min(b[j],a[j]+a[i]);
int u=get(t[0],t[1],t[2]);
if(!st.count(u))
{
if(!stc[t[2]]) res++,stc[t[2]]=true;
st[u]=true;
dfs(t);
}
}
return res;
}
int solve()
{
res=0;
st.clear();
memset(stc,false,sizeof stc);
int p[]={0,0,b[2]};
return dfs(p);
}
int main()
{
while(cin>>b[0]>>b[1]>>b[2])
cout<<solve()<<endl;
return 0;
}
哦,我的朋友,如果可以的话想请教你一下,为什么不用f[N][N]来记录a,b的使用状态呢?