HDU5396 / 15多校9-1 Expression

题意

给出了一个算术表达式，表达式里面只会含有加减乘三种运算。我们每一次从中选取两个数字并执行这两个数字对应的运算，运算结果放回式子中继续进行运算，直到最后只剩下了一个数。让我们求的是每一种不同的选取方式所得到的结果的和。

注意

这个题没有做好的主要原因是没有领会到题目中关于不同的选取方式的定义，注意到题目中讲到只要有一轮选取的数字不一样，就视为不同。这句话的含义中有两个信息：一是允许重复，二是要分先后。

思路

最开始确实是没什么思路的，后来看了看board发现并不是特别难的题。于是尝试拆解问题，我们可以从算数式的一小段入手，以sample的1 + 4 * 6 – 8 * 3为例。

只考虑1 + 4部分，只有一种配置方法，就是(1 + 4);
考虑1 + 4 * 6部分，我们发现这一部分可以看成两种情况：1 + (4 * 6)和(1 + 4) * 6，在这里面我们已经考虑了1 + 4区段，而4 * 6区段只有一种配置。这样1 + 4 * 6这个区段就有两种配置了。
接下来考虑1 + 4 * 6 – 8区段，要想得到这个区段的全部情况，我们应该考虑：
1 + (4 * 6 – 8),1 + 4 * (6 – 8),(1 + 4) * 6 – 8,(1 + 4 * 6) – 8这些情况，其中(4 * 6 – 8)又可以看成考虑(4 * 6) – 8,4 * (6 – 8)这两种情况，而(1 + 4 * 6)的对应情况我们先前已经算好了。
最后，考虑1 + 4 * 6 – 8 * 3，顺着上面的思路来，就可以拆分成：
1 + (4 * 6 – 8 * 3),1 + 4 * (6 – 8 * 3),(1 + 4) * 6 – (8 * 3),(1 + 4 * 6) – 8 * 3,(1 + 4 * 6 – 8) * 3，接下来再去拆分这五种情况中的子情况。。。

如果比较敏感的话应该已经发现这就是典型的区间dp了，在推方程的时候，我们是将所有子情况的答案累加，得到当前情况的答案，但这还不够，还要注意每种情况，因为选择顺序的关系，会有多重副本，而这个副本的数量其实蛮好求，就是阶乘，而还要注意，我们在讨论当前情况的时候，是将整个等待处理的算式区段分成了（左区段）算子（分界点）算子（右区段）这样看待的，那么先后的问题又来了，我们不光左右区段的答案自身要乘上阶乘，最后整个结果还要乘上一个组合数，因为左右区段的操作又是分先后的。

以下引自官方题解，注意第2段第2行的dp[l][r]实际上是dp[l][k]。

 

代码

测试数据