题解 P1236 【算24点】

· · 题解

来自一个懒蒟蒻的题解……

看到各位巨佬都写得那么长，其实远不比这样。

首先，我们可以先假设运行顺序必然是从左到右，因此我们便需要一个从左到右的全排列，然后再进行判断，全排列大家都知道怎么写，没错，就是dfs！

void dfs(int dep){
    if(flag2) return ;
    if(dep==5){
        for(int i=1;i<=4;i++) //枚举三个运算符
        for(int j=1;j<=4;j++)
        for(int k=1;k<=4;k++){
            flag=1;
            if(f(k,f(j,(f(i,a[1],a[2])),a[3]),a[4])==24&&flag){output(1,i,j,k);flag2=1;return ;}
        }
    }
    for(int i=1;i<=4;i++)
        if(!v[i]){
            v[i]=1;
            a[dep]=c[i];
            dfs(dep+1);
            v[i]=0;
        }
}

我们用f函数来进行计算，用flag来判断不合适的情况。

再加上一个判断和输出，貌似此题就已经解决了，但是却没有过，什么原因？来看一则样例：

6 7 8 9

答案应该是：

8*6=48

9-7=2

48/2=24

我们发现在8*6=48后，没有立即再用48，而是先算9-7=2。所以还有一种情况，那就是先算前两者，再算后两者，它们之间再进行运算。这样问题就解决了。

最后献上最短代码：

#include<bits/stdc++.h>
using namespace std;
int a[5],c[5],v[5];
bool flag,flag2;
int f(int t,int x,int y){
    if((t==4&&(!y||x%y!=0||x<y))||(t==2&&x<y)) return -999;
    if(t==1) return x+y;
    if(t==2) return x-y;
    if(t==3) return x*y;
    if(t==4) return x/y;
}
char pd(int x){
    if(x==1) return '+';
    if(x==2) return '-';
    if(x==3) return '*';
    if(x==4) return '/';
}
void output(int p,int i,int j,int k){
    if(p==1){
        printf("%d%c%d=%d\n",max(a[1],a[2]),pd(i),min(a[1],a[2]),f(i,a[1],a[2]));
        printf("%d%c%d=%d\n",max(f(i,a[1],a[2]),a[3]),pd(j),min(f(i,a[1],a[2]),a[3]),f(j,f(i,a[1],a[2]),a[3]));
        printf("%d%c%d=%d\n",max(f(j,f(i,a[1],a[2]),a[3]),a[4]),pd(k),min(f(j,f(i,a[1],a[2]),a[3]),a[4]),f(k,f(j,f(i,a[1],a[2]),a[3]),a[4]));
    }
    else{
        printf("%d%c%d=%d\n",max(a[1],a[2]),pd(i),min(a[1],a[2]),f(i,a[1],a[2]));
        printf("%d%c%d=%d\n",max(a[3],a[4]),pd(k),min(a[3],a[4]),f(k,a[3],a[4]));
        printf("%d%c%d=%d\n",max(f(i,a[1],a[2]),f(k,a[3],a[4])),pd(j),min(f(i,a[1],a[2]),f(k,a[3],a[4])),f(j,f(i,a[1],a[2]),f(k,a[3],a[4])));
    }
}
void dfs(int dep){
    if(flag2) return ;
    if(dep==5){
        for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
        for(int k=1;k<=4;k++){
            flag=1;
            if(f(k,f(j,(f(i,a[1],a[2])),a[3]),a[4])==24&&flag){output(1,i,j,k);flag2=1;return ;}
            if(f(j,f(i,a[1],a[2]),f(k,a[3],a[4]))==24&&flag){output(2,i,j,k);flag2=1;return ;}
        }
    }
    for(int i=1;i<=4;i++)
        if(!v[i]){
            v[i]=1;
            a[dep]=c[i];
            dfs(dep+1);
            v[i]=0;
        }
}
int main(){
    for(int i=1;i<=4;i++) scanf("%d",&a[i]);
    for(int i=1;i<=4;i++) c[i]=a[i];
    dfs(1);
    if(!flag2) printf("No answer!");
    return 0;
}

THE END.