HDU-5396 Expression 题解

本文距离上次更新已过去 0 天，部分内容可能已经过时，请注意甄别。

HDU 5396 Expression

看到 这么小的范围就不难想到区间 DP。

表示从第 个数到第 个数的结果和。考虑枚举到第 个位置运算符。

如果 是 ：
考虑 ，其中 是结果的序列。由乘法原理可知：，。考虑左右边分别有多少个运算符即可。
那么

所以同理，如果 是 ，则 ；
如果 是 ，则 。

……对，对吗？
在愉快地爆掉样例后，发现了递推式中的错误：即使运算符左右两边的结果是确定的，也可能有不同的运算过程。可能是先把左边的运算符算完了，再算右边的运算符；也可能是先算左边的一个、再算右边的一个……所以，我们还得考虑运算符的运算顺序。可以把问题转化成：现在有一个长为 的运算符序列，要挑 （或 ）个运算符放在左/右边，问有几种做法。那答案显然是 （或）了。所以最终的转移方程为：

边界条件： 为原序列第 个数。记得取膜。代码不放了。