← 返回题单
题单练习 深度优先搜索
← 上一题 下一题 →

A6275 | Welcome24ever 和代数

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

最近，Welcome24ever 又在代数课上得了不太好的分数。为了避免今后再次出现这种令人不快的事情，Welcome24ever 决定练习自己的算术能力。

他在黑板上写下了四个整数 $a, b, c, d$。在接下来的三分钟里，他每分钟会进行一次操作：

  • 每次从黑板上任选两个数字（不要求相邻），
  • 用它们的和或者积替换这两个数（即把这两个数擦掉，写上它们的和或积），

    • 三次操作之后，黑板上就只剩下一个数字。

    不幸的是，由于他记性很差，他忘记了最后得到的那个数字。但他还记得：
  • 起初写下的四个数 $a, b, c, d$；
  • 三次操作中，每一步是“加法”还是“乘法”，也就是操作符的顺序；
  • 以及他当时因为结果非常小而感到十分惊讶。
请你帮助 Welcome24ever 回忆这个数字：在给定最初四个数，以及三次操作符的顺序（每次只能从加法和乘法中选），通过合理选择每一步要“合并”的那一对数，使得最后结果尽可能小，并输出这个最小可能值。

输入格式

第一行包含四个整数 $a, b, c, d$（$0 \le a, b, c, d \le 1000$），表示最初写在黑板上的四个数。

第二行包含三个用空格分隔的符号，每个符号为 '+' 或 '*'，依次给出三次操作中使用的运算类型：

  • '+' 表示该步操作必须使用加法；
  • '*' 表示该步操作必须使用乘法。
你可以在每一步任选当前仍在黑板上的两个数进行该步指定运算。

输出格式

输出一个整数，表示在给定运算顺序下，最终可能得到的最小结果。

输入输出样例

输入 #1
1 1 1 1
+ + *
输出 #1
3
输入 #2
2 2 2 2
* * +
输出 #2
8
输入 #3
1 2 3 4
* + +
输出 #3
9
C++ 编辑器
输入
输出