noip2015子串
这题的话是一道很难的动归题（至少对我来说），本人之前的字符串功底就不咋地，所以见谅了，题解可能啰嗦一些。
首先先把数组构建出来。对于字符串的题目，一般来说写动归都是分字符来处理，所以就是f[i][j]然后其中还有一个数组k，表示分成的组，所以开三维f[i][j][k]表示A串前i个字符（i必须取到），B串前j个字符（j必须取到）分成k个子串的方案数。
如果a[i]!=b[j]，由于i和j都要取到，明显不可以，所以一个方案也没有。
如果a[i]==b[j],那么首先第一种就是f[1][j][k-1]+f[2][j][k-1]+……+f[i-1][j][k-1]，即相当于把a[i]和b[i]分别看成一个子串。
另一种就是f[i-1][j-1][k]，即接着上一个串。这样的动归方程就基本推出来了（现在推推感觉好简单，之前为啥想不到？苦恼ing）
当然我们需要一些预处理和优化。预处理就是预处理f[i][j][1]的情况。很简单，再此不在赘述。优化的话时间和空间都要优化。
首先空间会爆，那就滚k就Ok了
其次时间会爆，主要是用于处理f[1][j][k-1]+f[2][j][k-1]+……+f[i-1][j][k-1]这一坨，那么明显可以使用另一个sum数组求和就Ok了。
注意：我们最后求出来的是f[1][m][k]+……f[n][m][k]，即sum[n][m][k]而不是f[n][m][k].
这里在多说几句，对于字符串动态规划的处理，大部分的状态转移都是从上一个或上几个字符转移到当前字符的。而且很多都是求方案总数的。这些题注意一下几点
1. f数组的意义，特别是：i是必须取还是必须不取还是可取可不取
2. 转移的条件（来自题目）：细节问题，全面问题
3. 后面用动态规划惯例的方法来思考优化
4. 重点：预处理。这一步不能漏。我写这道题的时候就没写预处理交上去0分的。字符串的预处理其实不难，从最简单的情况来考虑，吧第一个数组预处理完毕，就可以了。主要是怕忘记。