POJ 2787:算24

2787:算24

查看
提交
统计
提示
提问
总时间限制:

3000ms
内存限制:

65536kB
描述

给出4个小于10个正整数，你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是，是否存在一种方式使得得到的表达式的结果等于24。这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致（这里的除法定义是实数除法）。比如，对于5，5，5，1，我们知道5 * (5 – 1 / 5) = 24，因此可以得到24。又比如，对于1，1，4，2，我们怎么都不能得到24。
输入

输入数据包括多行，每行给出一组测试数据，包括4个小于10个正整数。最后一组测试数据中包括4个0，表示输入的结束，这组数据不用处理。
输出

对于每一组测试数据，输出一行，如果可以得到24，输出“YES”；否则，输出“NO”。
样例输入

5 5 5 1 1 1 4 2 0 0 0 0

样例输出

YES NO

思路

用一个数组存四个数，然后dfs找一个前置数（前置数不能vis过），一个后置数，后置数打标记，然后前置数和后置数进行四则运算保存在前置数中（注意除数不能为0），当递归深度为3时，看看那个没有vis过的前置数是不是24，判断方法

[abs(val[i]-24.0)<0.001 ]

别忘记dfs之后，要还原前置数的值并清除后置数的vis标记，进行回溯

#include <iostream>
#include<bits/stdc++.h>
#define each(a,b,c) for(int a=b;a<=c;a++)
#define de(x) cout<<#x<<" "<<(x)<<endl
using namespace std;

const int maxn=100+5;
const int inf=0x3f3f3f3f;

double val[4];
bool vis[4];
bool flag;
void dfs(int depth)
{
    if(depth==3)
    {
        each(i,0,3)
        {

            if(abs(val[i]-24.0)<0.001&&vis[i]==false)flag=true;
        }
    }
    for(int i=0;i<=3;i++)
    {
        if(vis[i])continue;
        each(j,0,3)
        {
            if(i==j||vis[j])continue;
            vis[j]=true;
            double a=val[i];double b=val[j];
            val[i]=a+b;dfs(depth+1);
            val[i]=a-b;dfs(depth+1);
            val[i]=a*b;dfs(depth+1);
            if(b!=0.0)val[i]=a/b,dfs(depth+1);
            val[i]=a;/////////////////////////////////////////////
            vis[j]=false;
        }

    }
}
/*
5 5 5 1
1 1 4 2
0 0 0 0
*/

int main()
{

    while(scanf("%lf %lf %lf %lf",&val[0],&val[1],&val[2],&val[3]))
    {

        if(val[0]==0&&val[1]==0&&val[2]==0&&val[3]==0)break;
        memset(vis,0,sizeof(vis));
        flag=false;
        dfs(0);
        flag?puts("YES"):puts("NO");
    }
}