题意:给你一个表达式。每次都可以选取相邻的两个数以及期间的符号进行操作。每次选择不同,得到的结果不同,求所有不同的操作得到的值的和。

思路:以最后一次操作为入手点。 假设最后一次操作为某个符号, 那么就是两边的所有的操作的得到的值进行最后一次操作。

然后就可以看出是很明显的区间dp了。

dp[l,r]

表示l,r这段数能形成的答案总和。

枚举最后一步操作k,如果是乘法,答案为dp[l,k]*dp[k+1,r]dp​[l,k]dp​[k+1,r],由于分配率这个会乘开来。

如果是加法那么是dp[l,k]*(r-k-1)!+dp[k+1,r]*(k-l)!,即要乘上右边[k+1,r]这些数所有可行的方案数,减法同理。

最后乘上C(r-l-1, k-l),即把两边操作合起来的方案数。

这个dp很重要的一点就是求和要和求方案数分开来想,否则就会混乱不堪。

 

HDU 4745 Two Rabbits(区间dp,最长环形回文串)

题意:给定一串环形数,两个兔子可以任选一个起点一个向左跳,一个向右跳,不可回头,两个兔子每次跳的位置数字要相同,并且 可以在同一个位置上,求最多可以...

阅读全文

HDU 4283 You Are the One (2012天津,区间dp)

题意:给定一个队列,有一个栈,你可以通过这个栈来获取一个新队列的顺序。比如队列最前面的元素可以先进栈,最后再入新的队,得到的序列的 sigma((i-1)*a[...

阅读全文

UVA 10688 – The Poor Giant (区间dp)

题意:重量越大的苹果越酸,越轻的越苦,中间的正好,一堆苹果中恰有一个苹果是甜的,找出这个苹果所需要的最小代价和。 思路:区间dp。 比较水,我们选了一...

阅读全文

欢迎留言

*