题解洛谷P1236 【算24点】

萌新首发暴力题解，大佬忽喷

不得不说，个人认为许多大佬们把程序想复杂了，所以码量很长，但是实际上这题并不要这么复杂。。。

可以考虑用一个\(dfs\)维护一个状态\(f(n)[a_1,a_2……a_n]\)

接下来我们暴力枚举两两配对的方案，对于每个\(a[i]\)，\(a[j]\)只要算出两数的较大值和较小值再进行模拟加减乘除运算即可。

至于评论区里提到的反减和反除其实是不必考虑的，试想我们每次都是用较大值减较小值，较大值除较小值，也就不可能出现小减大或者小除大的情况。

而对于\(a[i]\)，\(a[j]\)两两配对，可以将他们运算的结果存入\(a[i]\)，而\(a[j]\)可以存\(a[n]\)的量。说白了就是简单的滚动数组啦~

那么这个状态就被压缩成了\(f(n-1)[a_1,a_2……a_{n-1}]\)，继续\(dfs\)。

对于边界处理，即当\(n=1\)时状态变为了\(f(1)[a_1]\)，\(a_1\)就是最终结果。若\(a_1=24\)说明成立，过程在每次运算中维护就\(ok\)了。

#include<bits/stdc++.h>

using namespace std;

int num[10],f[20];

char ch[10];

bool Game(int n){

    if(n==1){//边界

        if(num[1]==24)return true;//判结果

        else return false;

    }

    for(int i=1;i<=n;i++){

        for(int j=i+1;j<=n;j++){//两两匹配,即可模拟所有可能

            int ti=num[i],tj=num[j];//保留原结果

            int a=max(ti,tj);

            int b=min(ti,tj);//取较大较小值

            int t=4-n;

            num[j]=num[n];//压缩数组

            //初始化

			f[t*3+1]=a;

			f[t*3+2]=b;

			f[t*3+3]=a+b;

			ch[t+1]='+';//记录运算过程

            num[i]=a+b;//做加法

            if(Game(n-1))return true;//DFS 

			f[t*3+1]=a;

			f[t*3+2]=b;

			f[t*3+3]=a-b;

			ch[t+1]='-';//记录运算过程

        	num[i]=a-b;//做减法

            if(Game(n-1))return true;//DFS 

            f[t*3+1]=a;

			f[t*3+2]=b;

			f[t*3+3]=a*b;

			ch[t+1]='*';//记录运算过程

            num[i]=a*b;//做乘法

            if(Game(n-1))return true;//DFS 

            if(b!=0&&a%b==0){//判断是否除的尽

            	if(a/b>=1){

            		f[t*3+1]=a;

					f[t*3+2]=b;

					f[t*3+3]=a/b;

					ch[t+1]='/';//记录运算过程

            		num[i]=a/b;//做除法

                    if(Game(n-1))return true;//DFS

				}

            }

            num[i]=ti;

            num[j]=tj;//答案错误还原之前结果

        }

    }

    return false;

}

int main(){

    for(int i=1;i<=4;i++){

        cin>>num[i];

    }

    if(Game(4)){

    	cout<<f[1]<<ch[1]<<f[2]<<'='<<f[3]<<endl;

    	cout<<f[4]<<ch[2]<<f[5]<<'='<<f[6]<<endl;

    	cout<<f[7]<<ch[3]<<f[8]<<'='<<f[9]<<endl;//暴力输出

	}else{

		cout<<"No answer!"<<endl;

	}

    return 0;

}

\(\operatorname{Update} \operatorname{On} \operatorname{2018.12.01}\)

巴特西

题解洛谷P1236 【算24点】

萌新首发暴力题解，大佬忽喷

最新文章

热门文章

巴特西

题解 洛谷P1236 【算24点】

萌新首发暴力题解，大佬忽喷

最新文章

热门文章

题解洛谷P1236 【算24点】