[数据结构与算法]AcWing 4213. 最小结果（深搜）

有四个整数 a,b,c,d。

有三个操作符 op1,op2,op3，每个操作符要么是 *（表示乘法），要么是 +（表示加法）。

现在，我们要进行如下操作：

从现有整数中选出两个，按 op1 进行运算，得到结果。将选出的两个整数舍弃，并将结果保留。此时我们还剩下三个整数。

从现有整数中选出两个，按 op2 进行运算，得到结果。将选出的两个整数舍弃，并将结果保留。此时我们还剩下两个整数。

从现有整数中选出两个，按 op3 进行运算，得到结果。将选出的两个整数舍弃，并将结果保留。此时我们只剩下一个整数。
我们希望，最后剩下的一个整数尽可能小。

输入格式
第一行包含四个整数 a,b,c,d。

第二行包含三个操作符 op1,op2,op3，每个操作符要么是 *，要么是 +。

输出格式
输出最后剩下的一个整数的最小可能值。

数据范围
所有测试点满足 0≤a,b,c,d≤1000。

输入样例1：
1 1 1 1
++*
输出样例1：
3

输入样例2：
2 2 2 2
**+
输出样例2：
8

输入样例3：
1 2 3 4
*++
输出样例3：
9

用 一个变长数组 v 表示 每次操作之后剩余的元素 和 一个整数 u 表示 当前用到的第 u+1 个操作符 op[u] ，用这两个参数共同代表递归搜索树中一个节点的状态。

当v的大小为1时，即只剩下一个数字时更新ans（答案），并回溯寻找其他分支。

#include<bits/stdc++.h>

using namespace std;
#define int long long
int a,b,c,d;
char op[3];

int ans = 1e18;

void dfs(vector<int> v,int u)
{
	if(v.size()==1)
	{
		ans = min(ans,v[0]);
		return ;
	}
	char oper = op[u];
	for(int i=0;i<v.size();++i)
	{
		for(int j=i+1;j<v.size();++j)
		{
//用一个新的vector t取代上一层的v，存储每次操作之后形成的元素集合
			vector<int> t;
			for(int k=0;k<v.size();++k)
			{
				if(k!=i&&k!=j) t.push_back(v[k]);
//由于i和j是我们每次进行操作符运算的两个元素的下标，因此我们要先将除了这两个元素之外，v数组中的元素压入数组
			}
			
//之后将v[i]和v[j]经过操作之后的结果压入t数组
			if(oper=='*') t.push_back(v[i]*v[j]);
			else t.push_back(v[i]+v[j]);
			dfs(t,u+1);//将t替代v进入下一层递归，并用下一个操作符
			t.pop_back();//恢复现场
		}
	}
}

signed main()
{
	cin>>a>>b>>c>>d>>op[0]>>op[1]>>op[2];
	vector<int> v(4);
	v = {a,b,c,d};	
	dfs(v,0);
	cout<<ans<<endl;
	
	return 0;
}