ALGO-995 试题 算法训练 24点

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　　24点游戏是一个非常有意思的游戏，很流行，玩法很简单：给你4张牌，每张牌上有数字（其中A代表1，J代表11，Q代表12，K代表13），你可以利用数学中的加、减、乘、除以及括号想办法得到24，例如：
　　((A*K)-J)*Q等价于((1*13)-11)*12=24
　　加减乘不用多说了，但除法必须满足能整除才能除！这样有一些是得不到24点的，所以这里只要求求出不超过24的最大值。

输入格式

　　输入第一行N(1<=N<=5)表示有N组测试数据。每组测试数据输入4行，每行一个整数(1到13)表示牌值。

输出格式

　　每组测试数据输出一个整数，表示所能得到的最大的不超过24的值。

样例输入

3
3
3
3
3
1
1
1
1
12
5
13
1

样例输出

24
4
21

这题我用了2个dfs做，一个是从左到右的优先级计算，一个是前两个与后两个先算的优先级计算。

代码挺长的，但都很规律（主要是一开始少考虑了第二个优先级加上之前写的时候打错字了然后找了很久的bug拖了很久时间，已经麻木了）不想优化的，能优化的话可以留言给我(来，让我康康你代码怎么样啊(误))

不多废话了代码如下_____________________________________________________________

#include<iostream>
#include<algorithm>
#include<stack>


#define INF 0x7ffffffffffffff
typedef long long ll;
using namespace std;


ll arr[4] = { 0 };//原数组
ll MAX = 0;
stack<ll>ans;//记录已经计算过的值
stack<ll>ans2;//第二种优先级的栈(其实可以不用开这个栈，用上面那个就可以的)

void dfs(ll x) {//x代表栈里有几个数了
	if (x == 3) {//栈里面有三个值的时候就可以出结果了，栈顶的即为运算结果
		if (MAX < ans.top() && ans.top() <= 24) MAX = ans.top();
		return;
	}

	for (ll i = 0; i < 4; i++) {//一般的加减乘除
		ll temp = 0;
		switch (i) {
		case 0: {
			if (ans.empty()) {
				temp = arr[x] + arr[x + 1];
				ans.push(temp);
				dfs(x + 1);
				ans.pop();
			}
			else {
				temp = ans.top();
				temp = temp + arr[x + 1];
				ans.push(temp);
				dfs(x + 1);
				ans.pop();
			}
			break;
		}
		case 1: {
			if (ans.empty()) {
				temp = arr[x] - arr[x + 1];
				ans.push(temp);
				dfs(x + 1);
				ans.pop();
			}
			else {
				temp = ans.top();
				temp = temp - arr[x + 1];
				ans.push(temp);
				dfs(x + 1);
				ans.pop();
			}
			break;
		}
		case 2: {
			if (ans.empty()) {
				temp = arr[x] * arr[x + 1];
				ans.push(temp);
				dfs(x + 1);
				ans.pop();
			}
			else {
				temp = ans.top();
				temp = temp * arr[x + 1];
				ans.push(temp);
				dfs(x + 1);
				ans.pop();
			}
			break;
		}
		case 3: {
			if (ans.empty()) {
				if (arr[x] % arr[x + 1] == 0) {
					temp = arr[x] / arr[x + 1];
					ans.push(temp);
					dfs(x + 1);
					ans.pop();
				}
				else return;
			}
			else {
				temp = ans.top();
				if (temp % arr[x + 1] == 0) {
					temp = temp / arr[x + 1];
					ans.push(temp);
					dfs(x + 1);
					ans.pop();
				}
				else return;
			}
			break;
		}
		}
	}
	return;
}

void dfs2(ll x) {//第二种优先级
	if (x == 3) {
		if (MAX < ans2.top() && ans2.top() <= 24) MAX = ans2.top();
		return;
	}
	if (x == 2&&ans2.size()==2) {

		ll temp1 = 0, temp2 = 0;
		temp2 = ans2.top(); ans2.pop();
		temp1 = ans2.top();
		ans2.push(temp2);
		for (ll i = 0; i < 4; i++) {
			ll temp = 0;
			switch (i) {
			case 0: {
				temp = temp1 + temp2;
				ans2.push(temp);
				dfs2(x + 1);
				ans2.pop();
				break;
			}
			case 1: {
				temp = temp1 - temp2;
				ans2.push(temp);
				dfs2(x+1);
				ans2.pop();
				break;
			}
			case 2: {
				temp = temp1 * temp2;
				ans2.push(temp);
				dfs2(x+1);
				ans2.pop();
				break;
			}
			case 3: {

				if (temp2!=0&&temp1 % temp2 == 0) {
					temp = temp1 / temp2;
					ans2.push(temp);
					dfs2(x + 1);
					ans2.pop();
				}
				else return;
				
				break;
			}
			}
		}

		return;
	}
	
	for (ll i = 0; i < 4; i++) {
		ll temp = 0;
		switch (i) {
		case 0: {
			if (ans2.empty()) {
				temp = arr[0] + arr[1];
				ans2.push(temp);
				dfs2(x + 1);
				ans2.pop();
			}
			else {
				temp = arr[2] + arr[3];
				ans2.push(temp);
				dfs2(x + 1);
				ans2.pop();
			}
			break;
		}
		case 1: {
			if (ans2.empty()) {
				temp = arr[0] - arr[1];
				ans2.push(temp);
				dfs2(x + 1);
				ans2.pop();
			}
			else {
				temp = arr[2] - arr[3];
				ans2.push(temp);
				dfs2(x + 1);
				ans2.pop();
			}
			break;
		}
		case 2: {
			if (ans2.empty()) {
				temp = arr[0] * arr[1];
				ans2.push(temp);
				dfs2(x + 1);
				ans2.pop();
			}
			else {
				temp = arr[2] * arr[3];
				ans2.push(temp);
				dfs2(x + 1);
				ans2.pop();
			}
			break;
		}
		case 3: {
			if (ans2.empty()) {
				if (arr[0] % arr[1] == 0) {
					temp = arr[0] / arr[1];
					ans2.push(temp);
					dfs2(x + 1);
					ans2.pop();
				}
				else return;
			}
			else {
				if (arr[2] % arr[3] == 0) {
					temp = arr[2] / arr[3];
					ans2.push(temp);
					dfs2(x + 1);
					ans2.pop();
				}
				else return;
			}
			break;
		}
		}
	}
}

int main() {
	ll n = 0;
	cin >> n;
	while (n--) {
		fill(arr, arr + 4, 0);
		MAX = 0;
		for (ll i = 0; i < 4; i++) cin >> arr[i];
		sort(arr, arr + 4);//全排列必须数组升序，否则排列结果会省略
		do{
			dfs(0);//从左到右优先计算
			dfs2(0);//前两个与后两个优先计算
		} while (next_permutation(arr, arr + 4));
		//cout << "                               ";
		cout << MAX << endl;
	}

	return 0;
}

_____________________________________________________________________________

结果如下，搞个ac废了不少时间，让我输的折磨车底...