首页 > ACM题库 > HDU-杭电 > HDU 1427 速算24点-DFS-[解题报告] C++
2013
12-10

HDU 1427 速算24点-DFS-[解题报告] C++

速算24点

问题描述 :

速算24点相信绝大多数人都玩过。就是随机给你四张牌,包括A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)。要求只用’+',’-',’*',’/'运算符以及括号改变运算顺序,使得最终运算结果为24(每个数必须且仅能用一次)。游戏很简单,但遇到无解的情况往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌,判断是否有解。我们另外规定,整个计算过程中都不能出现小数。

输入:

每组输入数据占一行,给定四张牌。

输出:

每一组输入数据对应一行输出。如果有解则输出"Yes",无解则输出"No"。

样例输入:

A 2 3 6
3 3 8 8

样例输出:

Yes
No

HDU-1427-速算24点

http://acm.hdu.edu.cn/showproblem.php?pid=1427

4个数通过 +,—,*,/和加括号,计算得24,

枚举数字和运算符,DFS即可,注意题目要求计算过程中都不能出现小数,所以做除法时稍作处理

枚举数组可用algorithm里的next_permutation

The next_permutation() function attempts to transform the given range of elements [start,end) into the next lexicographically greater permutation of elements. If it succeeds, it returns true, otherwise, it returns false. 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int flag;
int num[4];
int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}
void dfs(int sum,int cur,int m)
{
	if(flag)
	return;
	if(m==3)
	{
		if(sum+cur==24||sum-cur==24||sum*cur==24)
		flag=1;
		if(cur!=0&&sum%cur==0&&sum/cur==24)
		flag=1;
		return;
	}
	dfs(sum+cur,num[m+1],m+1);  //先计算前一部分
	dfs(sum-cur,num[m+1],m+1);
	dfs(sum*cur,num[m+1],m+1);
	if(cur!=0&&sum%cur==0)
	dfs(sum/cur,num[m+1],m+1);
	dfs(sum,cur+num[m+1],m+1);  //先计算后一部分,相当于加括号
	dfs(sum,cur-num[m+1],m+1);
    dfs(sum,cur*num[m+1],m+1);
	if(num[m+1]!=0&&cur%num[m+1]==0)
	dfs(sum,cur/num[m+1],m+1);
}
int main()
{
	int i;
	char str[5];
	while(scanf("%s",str)!=EOF)
	{
		if(strlen(str)==2)
		num[0]=10;
		else
		{
			if(str[0]==’A')
			num[0]=1;
			else if(str[0]==’J')
			num[0]=11;
			else if(str[0]==’Q')
			num[0]=12;
			else if(str[0]==’K')
			num[0]=13;
			else
			num[0]=str[0]-’0′;
		}
		for(i=1;i<=3;i++)
		{
			scanf("%s",str);
			if(strlen(str)==2)
		    num[i]=10;
		    else
			{
			   if(str[0]==’A')
			   num[i]=1;
			   else if(str[0]==’J')
			   num[i]=11;
			   else if(str[0]==’Q')
			   num[i]=12;
		       else if(str[0]==’K')
		       num[i]=13;
			   else
			   num[i]=str[0]-’0′;
			}
		}
		qsort(num,4,sizeof(num[0]),cmp);
		flag=0;
		do
		{
			dfs(num[0],num[1],1);
		}while(next_permutation(num,num+4)&&!flag);
		if(flag)
		printf("Yes\n");
		else
		printf("No\n");
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/cambridgeacm/article/details/7751678


,
  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept