本文共 2428 字，大约阅读时间需要 8 分钟。

题目大意

24点游戏。

解

原题：顺序可调换

由于顺序可以打乱，直接暴力dfs看看能不能合成24。

顺序不可调换

啊啊，挺头裂的。

TJH：我不清楚对不对啊 就暴搜啊

好。vector，我不会。再见。

于是写了个DP。分区间处理结果…再合并。然后一个区间可能有多种结果…又再枚举出来、运算。

代码

原题：顺序可调换

#include
   
    #include
    
     #include
     
      using namespace std;int flag,b[11],a[11],t;void dfs(int now, int z){   	if(now == 4){   		if(z == 24) flag = 1;		return;	} 	for(int i = 1; i <= 4; ++i)		if(b[i] == 0){   			b[i] = 1;			dfs(now+1, z+a[i]);  //加减乘除			dfs(now+1, z-a[i]);			dfs(now+1, z*a[i]);			if(a[i] != 0) if(z % a[i] == 0) dfs(now+1, z/a[i]); //除法特别判断			b[i] = 0;		}}void work(){   	scanf("%d%d%d%d",&a[1], &a[2], &a[3], &a[4]);	memset(b, 0, sizeof(b));	flag = 0;	for(int i = 1; i <= 4; ++i){     //枚举第一个数		b[i] = 1;		dfs(1, a[i]);  //正或负		dfs(1, -a[i]);		if(flag == 1) break;		b[i] = 0;	} 	if(flag == 1) printf("1\n");	else printf("0\n");}int main(){   	freopen("game.in","r",stdin);	freopen("game.out","w",stdout);	scanf("%d", &t);  //多组数据	while(t--) work();	fclose(stdin);	fclose(stdout);}
     
    
   

顺序不可调换

（注释都不想打了…艹

#include
   
    #include
    
     #include
     
      using namespace std;int flag, s[10][10][10000], a[10], l[10][10], t;void work(){   	scanf("%d%d%d%d", &a[1], &a[2], &a[3], &a[4]);	memset(s, 0, sizeof(s));	memset(l, 0, sizeof(l));	l[1][1] = 1; l[2][2] = 1; l[3][3] = 1; l[4][4] = 1;	s[1][1][1] = a[1];	s[2][2][1] = a[2];	s[3][3][1] = a[3];	s[4][4][1] = a[4];	for(int len = 2; len <= 4; ++len)  // 长度 		for(int q = 1; q <= 5-len; ++q) // 起始			for(int d = q; d < q+len-1; ++d){    //断点：从q到d，从d+1到q+len-1				for(int jg1 = 1; jg1 <= l[q][d]; ++jg1) //前个区间的可能的结果					for(int jg2 = 1; jg2 <= l[d+1][q+len-1]; ++jg2){    //后个区间的可能的结果						s[q][q+len-1][++l[q][q+len-1]] = s[q][d][jg1] + s[d+1][q+len-1][jg2];						s[q][q+len-1][++l[q][q+len-1]] = s[q][d][jg1] - s[d+1][q+len-1][jg2];						s[q][q+len-1][++l[q][q+len-1]] = s[q][d][jg1] * s[d+1][q+len-1][jg2];						if(s[d+1][q+len-1][jg2] != 0) 						if(s[q][d][jg1] % s[d+1][q+len-1][jg2] == 0)							s[q][q+len-1][++l[q][q+len-1]] = s[q][d][jg1] / s[d+1][q+len-1][jg2];					}			}	for(int i = 1; i <= l[1][4]; ++i)		if(s[1][4][i] == 24) {   			printf("1\n");			return;		}	printf("0\n");}int main(){   	freopen("game.in","r",stdin);	freopen("game.out","w",stdout);	scanf("%d", &t);	while(t--) work();	fclose(stdin);	fclose(stdout);}