[tyvj2802/RQNOJ74]算24点
描述
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1~9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。
您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(2*2)/4是合法的，2*(2/4)是不合法的）。下面我们给出一个游戏的具体例子：
若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+3*7=24。计算过程：
2+1=3
7*3=21
21+3=24
本题不要求输出具体计算过程。
输入格式
只有一行，四个1到9之间的自然数。
输出格式
如果有解的话，只要输出“yes”。如果没有解则输出“no”。
注意：不要输出引号“”。
测试样例1
输入
1 2 3 7
输出
yes
试题分析：这道题看着简单，其实背后的反例要考虑周全。如:6 8 2 1：(6*8)/(2*1)=24
针对这种情况，我们要怎么办呢？难道用两个DFS合并为一个答案？
显然不是，只要用我们枚举到的a[i]/ans或a[i]-ans，a[i]*ans就可以了。（ans为当前DFS到的答案）
为什么这样做呢？这样单纯的a[i]/ans，那么上面那种两个组合相除的情况怎么办？
我们发现，当格式为上面的情况，我们只需要以8/(2*1)*6来DFS就好了
那万一a/(b*c)除不尽怎么办？ 用double就好了……当DFS到最后一个时，会把它乘回整数的
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
//#include<cmath>
using namespace std;
const int INF = 9999999;
#define LL long long
inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
int N,M;
int a[5];
char c;
bool vis[5];
bool t[5];
double sum[40];
bool aflag=false;
void dfs(int st,double ans){
if(st==4&&ans==24){
puts("yes");
aflag=true;
exit(0);
}
else if(st==4) return ;
for(int i=1;i<=4;i++) t[i]=vis[i];
for(int i=1;i<=4;i++){
int tmp=4,su=0;
if(vis[i]) continue;
vis[i]=true;
dfs(st+1,ans+a[i]);
dfs(st+1,ans-a[i]);
if(ans!=0) dfs(st+1,ans/a[i]);
if(ans!=0) dfs(st+1,ans*a[i]);
if(ans!=0&&a[i]>ans) dfs(st+1,a[i]/ans);
if(sum[i]>ans) dfs(st+1,a[i]-ans);
vis[i]=false;
}
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
for(int i=1;i<=4;i++){
cin>>c;
if(c=='A') a[i]=1;
else if(c=='J') a[i]=11;
else if(c=='Q') a[i]=12;
else if(c=='K') a[i]=13;
else a[i]=c-'0';
}
dfs(0,0);
if(!aflag) puts("no");
return 0;
}