C*++语言和C++语言非常相似然而C*++的程序有时会出现意想不到的结果。比如像这样的算术表达式:
- 表达式=基本式 / 表达式+基本式 / 表达式-基本式
- 基本式=增量 / 系数*增量
计算这样的表达式的值的方法:
- 首先是每个基本式进行计算然后按照正常的算术运算法则计算。
- 如果一个基本式包含“a++”则先进行乘法运算再使变量a權值+1;如果一个基本式包含“++a”,则先使变量a权值+1再进行乘法运算
- 然而基本式可以按任意顺序计算,这就是为什么计算结果是完全无法預料的你的任务就是去找到最大的可能结果。
第一行一个整数n,表示变量a的初始值第二行,一个合法的C*++表达式
共一行,一个整数ans表示最大可能结果。
题目的意思就是有很多个 a++ 或 ++a每个a++之前都有一个系数,a++ 或 ++a 进行的顺序可以随意求最后表达式最大值
其实题目tag不说昰贪心我会往DP上面想的
如果是贪心的话,很容易想到:因为a是逐渐增加的那么让小的数乘上小的a,让大的数乘上大的a就可以使值最大
證明 1:优先选择大数乘大a
假设a从 a 变成 a+1,有两个数 x x+1,那么有两种选择:
显然让 【大的数】 和 【大的a】 相乘比较赚
但是 a++ 和 ++a 的顺序对于结果有沒有影响呢
证明 2: a++ 和 ++a 的顺序对于结果无影响:
这也再次说明了贪心策略是【大的数】 和 【大的a】 相乘
贪心比较容易实现,复杂度也不会呔大