acwing第35场周赛最小结果

acwing第35场周赛最小结果

最小结果
题目链接
描述

给你四个数字，3种 *** 作符(只有加法和乘法两种)，在不改变 *** 作符顺序的情况下，每次 *** 作舍弃原来的数，保留结果，求可以得到的最小结果

思路

刚开始打算使用贪心来做如果是加法就选最大的两个数进行 *** 作，如果是乘法就选取最小的两个数进行 *** 作，卡在了第14个数据上后来听了y总的思路发现暴搜是最好的解法不会少情况，每次按 *** 作符全部进行 *** 作，取结果最小的为答案，不用考虑特殊情况的存在，因为数的数量比较少，时间复杂度近似为O(1)，其实是O(18)，下面是y总版代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
char op[5];
LL ans = 1e18;//最大值为3000的四次方会爆int
void dfs(vector v, int u)
{
    if (v.size() == 1) ans = min(ans, v[0]);
    else
    {
        for (int i = 0; i < v.size(); i ++)
            for (int j = i + 1; j < v.size(); j ++)
            {
                vector t;
                for (int k = 0; k < v.size(); k ++)
                    if (k != i && k != j) t.push_back(v[k]);
                if (op[u] == '*') t.push_back(v[i] * v[j]);
                else t.push_back(v[i] + v[j]);
                dfs(t, u + 1);
            }
    }
}
int main()
{
    vector v(4);
    for (int i = 0; i < 4; i ++) cin >> v[i];
    for (int i = 0; i < 3; i ++) cin >> op[i];
    dfs(v, 0);
    cout << ans << endl;
    return 0;
}