[2010年江苏省选拔赛第三轮 第一试 找零钱的洁癖]BFS、Hash、贪心

【题目大意】
给出N个数和一个X，问这些数最少用多少个加加减减可以得到X。
X<=0x7FFFFFFF
【算法分析】
显然，这是搜索题。
然后。。。我的是cheat的。
一开始我是写双向广搜，貌似没多少分。
然后我同学直接单向暴力：80分。。。
好吧，沿用这个单向暴力广搜，然后发现TLE的两个点的数据都是由2^0 2^1 2^2….. 2^32组成的。
然后就是从2^32一直弄下来贪心就行了。。。就是二进制
下面的BFS，爆队列的话，直接就return INF。
然后。。。这样就可以弱弱地AC了。
【其它】
求正解。。。
【CODE】
#include using namespace std;
typedef long long big;
const big N=1000003;
const big INF=0x7FFFFFFF;
struct link{big y,next;}g[N];
big e,ans,n;
big ls[N],step[N];
big list[N],X,a[N];

void init(){
e=0; memset(ls,0,sizeof(ls));
cin >> X;
n=0;
while (cin >> a[n]) n++;
sort(a,a+n);
}

big greedy(big mb){
big times=0;
for (big i=n-1;i>=0;i–){
times+=mb/a[i];
mb-=mb/a[i]*a[i];
}
if (mb) return INF;
return times;
}

big inhash(big k){
big key=(k+INF)%N;
for (big t=ls[key];t;t=g[t].next)
if (list[g[t].y]==k) return g[t].y;
return 0;
}

void ins(big zz){
e++;
big key=(big)((list[zz]+INF)%N);
g[e].y=zz;
g[e].next=ls[key];
ls[key]=e;
}

big bfs(){
if (X==0) return 0;
big head=0,tail=1,i,pos;
list[1]=0; step[1]=0;
while (head head++;
for (i=0;i tail++;
if (tail>=N-22) return INF;
step[tail]=step[head]+1;
if (list[head] else list[tail]=list[head]-a[i];
if (list[tail]==X) return step[tail];
pos=inhash(list[tail]);
if (pos) {tail–; continue;}
ins(tail);
}
}
}

int main(){
init();
ans=greedy(X);
big tmp=bfs();
ans=min(ans,tmp);
cout << ans << endl;
}