【DFS】算24点

[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;

}

描述

输入格式

输出格式

测试样例1

输入

输出

相关文章