http://www.lofter.com/postentry?from=search&permalink=1cb3058e_2d358ca
说有n个节点n条边组成一个圈，每个节点上面有一个数，边上有一个+或*，如果消掉某条边，其相邻两个节点就用这个运算符合并。这样一路消边到底，问用什么过程能让最后得到的数最大（dp题）
说有n个节点n条边组成一个圈，每个节点上面有一个数，边上有一个+或*，如果消掉某条边，其相邻两个节点就用这个运算符合并。这样一路消边到底，问用什么过程能让最后得到的数最大（dp题）
这题我竟然还是看着妹子的提示，知道用动归，然后竟然想了n久。还是功力和妹子比差的有点远，继续努力吧。
解法：
假设列子为：
，那么dp的状态转移方程为：
，那么dp的状态转移方程为：
dp(new) = {[1,max(2,3,4)],[2,max(1,3,4)],[3,max(1,2,4)],[4,max(1,2,3)]}
我们以[1,max(2,3,4)]做进一步展开，其他的类似
[1,max(2,3,4)]=max{1+max(2,3,4),1 * max(2,3,4)}=1+max(2,3,4)=1+max{2*max(3,4),4+max(2,3)}(这里注意没有3的原因是3和1是不相邻的，因此3和1是无法发生作用关系的)=1+max{2*(3+4),4+2*3}=1+14 = 15.
其他的式子类似。
这里注意有些中间的计算过程是一样的，因此，如果可以，将中间计算过程存储起来，在后续中不需计算了。这也是动归快的原因。
http://lixinzhang.github.io/qu-jian-xing-dp.html