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;
}
分享到:
相关推荐
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
算法-数塔(HDU-2084).rar
算术(HDU-6715).rar
算法-确定比赛名次(HDU-1285).rar
最短路(HDU-2544).rar
算法-连连看(HDU-1175)(包含源程序).rar
算法-命运(HDU-2571)(包含源程序).rar
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
算法-欧拉回路(HDU-1878)(包含源程序).rar
算法-免费馅饼(HDU-1176)(包含源程序).rar
算法-六度分离(HDU-1869)(包含源程序).rar