搞定洛谷P1236 - 算24点的解题思路解析
最编程
2024-02-01 11:00:18
...
不得不说,个人认为许多大佬们把程序想复杂了,所以码量很长,但是实际上这题并不要这么复杂。。。
可以考虑用一个\(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;
}
原文地址:https://www.cnblogs.com/Agonim/p/12080762.html
上一篇: 玩转24点:HJ67算法详解