http://acm.nyist.net/JudgeOnline/problem.php?pid=43
后缀法求值（http://blog.csdn.net/hzyhouzhiyuan/archive/2011/03/07/6229897.aspx），该方法不一定最适合这个题，但同样条例十分清晰简单，适合初学，该题还有另外一种高效的方法，简单说一下，比如有4个数，然后枚举出两个数再枚举一个运算符使4个数变成3个数，然后继续这样，最后变成1个数看是否为所有结果，该方法代码书写较繁琐，并且不容易得到所有种情况的表达式。
/* *该题还是应用表达式求值的后缀方法求解的，虽然该题用来不是那么方便， *但是能够很方便的给出所有种情况的后缀表达式，在这种题的变形中将得到很好的应用。 *如果不太了解后缀法求解请看文档： *http://blog.csdn.net/hzyhouzhiyuan/archive/2011/03/07/6229897.aspx */ #include<iostream> #include<algorithm> #include<stack> #include<cstring> #include <iterator> using namespace std; //根据给的数值个数罗列的各种情况的地图 int map[8][6]={ {2,0,1,1,1,1}, {3,0,0,2,1,1}, {4,0,0,1,2,1}, {4,0,0,0,3,1}, {5,0,0,1,1,2}, {5,0,0,0,2,2}, {5,0,0,0,1,3}, {5,0,0,0,0,4} }; int res[10],nums[10]; int n,sum,count_int,flag; stack<double> sta; //递归枚举所有位置的运算符号 void calculation(int relational[],int n) { //-1->+,-2->-,-3->*,-4->/ if(n == (count_int-1)) { //得到一种后缀表达式求解 for (int i=0;i<=2*(count_int-1);i++) { if(res[i]>=0) sta.push(nums[res[i]]); else { double t1,t2; t1=sta.top(); sta.pop(); t2=sta.top(); sta.pop(); switch(res[i]) { case -1:sta.push(t2+t1);break; case -2:sta.push(t2-t1);break; case -3:sta.push(t2*t1);break; case -4:sta.push(t2/t1);break; } } } if( (sta.top()-sum<1e-6 && sta.top()-sum>-1e-6) && flag==0) { cout<<"Yes"<<endl; flag=1; return; /*copy(res,res+2*count_int-1,ostream_iterator<int>(cout," ")); cout<<endl;*/ } return; } //枚举运算符得到一种后缀表达式 for (int j=1;j<=4;j++) { int x=2*n; for (;x<=count_int*2-1;x++) { if(res[x]==-5) { res[x]=-j; break; } } calculation(relational,n+1); res[x]=-5; } } int main() { 、、freopen("1.txt","r",stdin); int relational[10]={0,1,2,3,4,5,6,7,8,9}; cin>>n; while(n--) { flag=0; cin>>count_int>>sum; for (int i=0;i<count_int;i++) cin>>nums[i]; if(count_int==1) { if(nums[0]==sum) cout<<"Yes"<<endl; else cout<<"No"<<endl; continue; } //枚举全排列 do { for (int i=0;i<=7;i++) { memset(res,0,sizeof(res)); if(map[i][0]>count_int) break; int tem=0; for (int j=1;j<=count_int;j++) { res[tem++]=relational[j-1]; switch(map[i][j]) { case 4:res[tem++]=-5; case 3:res[tem++]=-5; case 2:res[tem++]=-5; case 1:res[tem++]=-5; default:break; } } calculation(relational,0); } }while(next_permutation(relational,relational+count_int)); if(flag!=1) cout<<"No"<<endl; } }
