題目大意：給出5個數字，順序可以任意排列，有三種運算：加、減、乘，不考慮優先級，按順序計算，判斷能否有一種方案得出的結果是23。
我的思路是先回溯出全排列，然后枚舉每個運算。
以下是我的代碼：
#include<stdio.h>
long a[6],t[6];
bool can,used[6];
void dfs2(long dep,long now)
{
if(can) return;
if(dep>5)
{
if(now==23)
can=true;
return;
}
dfs2(dep+1,now+t[dep]);
dfs2(dep+1,now-t[dep]);
dfs2(dep+1,now*t[dep]);
}
void dfs1(long dep)
{
if(can) return;
if(dep>5)
{
dfs2(2,t[1]);
return;
}
for(long i=1;i<=5;i++)
if(!used[i])
{
used[i]=true;
t[dep]=a[i];
dfs1(dep+1);
used[i]=false;
}
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%ld%ld%ld%ld%ld",&a[1],&a[2],&a[3],&a[4],&a[5])==5)
{
long sum=0;
for(long i=1;i<=5;i++) sum+=a[i];
if(sum==0) break;
can=false;
dfs1(1);
if(can) printf("Possible\n");
else printf("Impossible\n");
}
return 0;
}
posted on 2010-01-10 13:36
lee1r 閱讀(621)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索