Source - Click Here
Description
话说某一个月黑风高的晚上,一只褐色的狐狸快速地跳过了一只懒狗,并留下一个字符串“032089”和一个数字5。
这其中一定隐含了某些秘密!酷爱思考的你马上发现，这个字符串可以写成：“03+2+0*89”，结果为5。这是一个非常有趣的问题!
现在给出一个长度为N的数字字符串和一个数字T，要求插入最少的加号或者乘号，使得数字字符串的运算结果为T。运算符*号优先级高于+号，运算数可以有任意个前导0。
Input
输入不超过5组数据,每组数据两行。
每组数据的第1行为长度为N，只包含0~9的数字字符串，第2行为一个数字T。
输入T<0表示输入结束。
对于30%的数据,有1≤N≤10，0≤T≤50。
对于50%的数据,有1≤N≤15，0≤T≤200。
对于全部的数据,有1≤N≤20，0≤T≤200。
Output
输出一个数字单独占一行，表示最少需要添加的运算符(+号或*号)数，无解输出-1。
Solutions
不是很难的DP，不过网上全是搜索做法让我很不爽，于是就水一发blog吧。
考虑到这个字符串会拆分成若干个$+$和若干个$\times$的形式，而且$\times$的优先级是高于$+$的。因此可以考虑维护两个DP，分别处理$+$和$\times$的混合情况和单独$\times$的情况。
由此可以得到一个DP方程，$f(T,i)$表示1至$i$中，凑出答案$T$的最小次数。
通过枚举最后一部分是$+$或连续的一段$\times$，容易得到转移方程
$f(T,j)=min \begin{cases} f(T-num(i,j),i-1)+1\\g(T’,i,j)+f(T-T’,i-1)+1 \end{cases}$
其中，$num(i,j)$表示原字符串$i$到$j$位凑出的数字。
现在考虑一下如何求$g(T,i,j)$，表示$i$到$j$位只能用$\times$凑出$T$的最小次数。
由于只能使用$\times$，因此枚举第一个部分$\times$的位置，易得转移方程
$g(T,i,j)=g(\frac{T}{num(i,k)},k+1,j)+1,num(i,k) \, | \, T$
然后就搞完啦，时间复杂度$O(N^2T^2+N^2T)$。
这里写几点注意的。
由于我是在做$f$时候更新$g$，因此$g$的转移要从后往前更新(这样可以少开一维)。
在转移$g$的时候要注意0的情况(我就是没考虑好，然后爆20)。
CODE
CODE - Click Here