CF55B Smallest number

CF55B Smallest number

洛谷传送门

题目描述

Recently, Vladimir got bad mark in algebra again. To avoid such unpleasant events in future he decided to train his arithmetic skills. He wrote four integer numbers aa , bb , cc , dd on the blackboard. During each of the next three minutes he took two numbers from the blackboard (not necessarily adjacent) and replaced them with their sum or their product. In the end he got one number. Unfortunately, due to the awful memory he forgot that number, but he remembers four original numbers, sequence of the operations and his surprise because of the very small result. Help Vladimir remember the forgotten number: find the smallest number that can be obtained from the original numbers by the given sequence of operations.

输入格式

First line contains four integers separated by space: 0<=a,b,c,d<=10000<=a,b,c,d<=1000 — the original numbers. Second line contains three signs ('+' or '' each) separated by space — the sequence of the operations in the order of performing. ('+' stands for addition, '' — multiplication)

输出格式

Output one integer number — the minimal result which can be obtained.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

题意翻译

现有4个整数(均小于等于1000)，并给出三个运算符(均为+或*)。要求每次取出不一定相邻的两个数，并依次使用给出的运算符对这两个数进行运算，并将结果当做一个新数如此操作，直到只剩下一个数为止。 编程求出最后剩下数的最小值。 翻译贡献者UID：22930

---

题解：

暴搜。

搜索思路要选对。

注意，它是任意两两选择，并不是每次选择、运算之后，下一次选择都必须选上一次的结果。

所以我的第一份代码挂了

正确的搜索思路应该是两两枚举、标记、还原现场。

需要注意的操作是两个数运算之后的结果要存到其中一个数里，然后把另一个数打标记。这样处理的话要比很多人用的vector啥的简单很多。

还需要注意的是还原现场的操作。不能除以0。所以代码：

#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
const int INF=1e13;
int a[5];
char s[5];
bool v[5];
int ans;
void dfs(int step)
{
    if(step==4)
    {
        for(int i=1;i<=4;i++)
            if(!v[i])
                ans=min(ans,a[i]);
        return;
    }
    for(int i=1;i<=4;i++)
    {
        if(v[i])
            continue;
        for(int j=1;j<=4;j++)
        {
            if(v[j]||j==i)
                continue;
            int ori=a[j];
            if(s[step]=='+')
            {
                v[i]=1;
                a[j]+=a[i];
                dfs(step+1);
                a[j]=ori;
                v[i]=0;
            }
            else
            {
                a[j]*=a[i];
                v[i]=1;
                dfs(step+1);
                a[j]=ori;
                v[i]=0;
            }
        }
    }
}
signed main()
{
    for(int i=1;i<=4;i++)
        cin>>a[i];
    for(int i=1;i<=3;i++)
        cin>>s[i];
    ans=INF;
    dfs(1);
    cout<<ans;
    return 0;
}