学步园

这道题也没什么好说的，直接DFS就可以了，只是要注意一句话“The aim is to use some arithmetic on (some of) the five numbers to form the target number.”，注意黑体的some of。

代码（几乎没剪枝）：

#include <iostream><br /> #include <cstring><br /> using namespace std;<br /> int q,m,dest;<br /> int a[6];<br /> bool used[6];<br /> void dfs(int k)<br /> {<br /> for (int i=1; i<=5; i++)<br /> if (!used[i] && a[i]<=dest && dest-a[i]<q)<br /> {<br /> q=dest-a[i];<br /> m=a[i];<br /> }<br /> for (int i=1; i<=5; i++)<br /> if (!used[i])<br /> for (int j=i+1; j<=5; j++)<br /> if (!used[j])<br /> {<br /> int tmp=a[i];<br /> a[i]=a[i]+a[j];<br /> used[j]=true;<br /> dfs(k-1);<br /> used[j]=false;<br /> a[i]=tmp;<br /> a[i]=a[i]-a[j];<br /> used[j]=true;<br /> dfs(k-1);<br /> used[j]=false;<br /> a[i]=tmp;<br /> a[i]=a[j]-a[i];<br /> used[j]=true;<br /> dfs(k-1);<br /> used[j]=false;<br /> a[i]=tmp;<br /> a[i]=a[i]*a[j];<br /> used[j]=true;<br /> if (k!=2 ||(k==2 && tmp>=0 && tmp<=100000)) dfs(k-1);<br /> used[j]=false;<br /> a[i]=tmp;<br /> if (a[j]!=0 && a[i]%a[j]==0)<br /> {<br /> a[i]=a[i]/a[j];<br /> used[j]=true;<br /> dfs(k-1);<br /> used[j]=false;<br /> a[i]=tmp;<br /> }<br /> if (a[i]!=0 && a[j]%a[i]==0)<br /> {<br /> a[i]=a[j]/a[i];<br /> used[j]=true;<br /> dfs(k-1);<br /> used[j]=false;<br /> a[i]=tmp;<br /> }<br /> }<br /> }</p> <p>int main()<br /> {<br /> int cases;<br /> cin>>cases;<br /> for (int o=0; o<cases; o++)<br /> {<br /> for (int i=1; i<=5; i++)<br /> cin>>a[i];<br /> cin>>dest;<br /> memset(used,0,sizeof(used));<br /> q=1000;<br /> dfs(5);<br /> cout<<m<<endl;<br /> }<br /> return 0;<br /> }<br />