题目大意:

问题要求求出一串数中添加m个加号，n个减号和不多于p个括号的最小值。由于每个数字是由1～9的数字组成，所以不必考虑以0开头的情况。

 

分析：

首先我们来考虑只添加ｍ个加号的情况，很显然简化后的问题满足最优化原理，可以用动态规划解决。用d[I,j]表示前I个数中添j个加号的最小值,l(I,j)表示把I～j的数字看成一个数的值。

其动态方程如下：

  d[I,j]=min｛d[k,j-1]+l(k+1,i)｝(I>=j,j-1<=k<=I-1)

    再来考虑只添加n个减号的情况，由于不能在数串添加减号，所以就必须拿出第一个数来作牺牲。现在假设abcdefg添加2个减号的最小值为a-bcdef-g。因为a-bcdef-g=a-(bcdef+g)，所以只要求出bcdefg添1个加号的最大值，问题就解决了。求最大值的方法与求最小值类似，其动态方程如下：

 d[I,j]=max｛d[k,j-1]+l(k+1,i)｝(I>=j,j-1<=k<=I-1)

最后来考虑同时添加号，减号的情况。因为题目要求添加不多于p个的括号，所以我们在值最优的前提下必须尽量减少添加括号的数目，使其控制在p以内。我们发现可以对任何一个一般情况进行化简，使其在最优值不变的前提下，减少括号的数目。

例如最优值出现在a-(b+(c-de)+fgh)-ij-(kl+mn);

a-(b+(c+de)+fgh)-ij-(kl+mn)

   =a-b-c-de-fgh-ij-kl-mn

   =a-(b+c+de+fgh)-ij-kl-mn

所以无论什么情况均可以转换成只添加一个加号的情况。又因为1<=p，所以问题就可以进行进一步转化为只有减号的情况,且不添括号的情况。例如:

a-(b+c+de+fgh)-ij-kl-mn= a-b-c-de-fgh-ij-kl-mn.

 

总结：

     因为p大于1，所以p的值对问题的答案就产生不了影响，可不必考虑。当n=0时，问题就可以转化为添加m个加号且不添加括号；当n>0时，问题就转化为添加m+n个减号的情况（可以先求扣去第一个数字后添加m+n-1个加号）。由于问题答案与中间得数均较大，应采用高精度计算，动态规划可采用双阶段滚筒式方法优化问题的空间需求。