不懂了。跟着不知道哪里来的题单做一做。
dp是一个dag(除了spfa，但是spfa真的算是dp吗?)，然后每个点是一个计算单元，它接收前面的点的计算结果并进行加工，作为自己的计算结果，不妨将这样的东西称为计算网络，当然这是胡乱叫的，不要把这个名字拿出去说是我起的，并且你应该自己起一个/xia
如果想要计算满足某些条件的什么东西的个数，现在我们已经会用一个计算网络计算一个东西是否满足要求，那么我们就可以通过对计算网络计数，而不是对东西计数，来解决这个问题。
如果计算网络有一些很好的性质，比如可以分成若干层，转移只和当前层相关，那么我们就可以只保留一层，从而极大缩减状态数。
以前我尝试把它抽象成dfa，但是它看起来并没有计算网络这么普遍。
爆炸oj3864 Hero meet devil
给一个agct串\(s\)，对于每个\(0\leq i\leq\vert s\vert\)，求所有长\(m\)的agct串\(t\)中有多少满足\(s,t\)的lcs长度是\(i\)。\(\vert s\vert\leq 15,m\leq 1000\)，答案膜\(10^9+7\)。
打一下 恶魔 你会发现它是 emo，所以实际上国王只是得了严重的抑郁症，以至于他的精神有时错乱了（
所以为什么我要帮助emo/xia
考虑我们怎么求一个。经典做法是，设\(dp(i,j)\)表示\(s\)中前\(i\)个和\(t\)中前\(j\)个的lcs，那么\(dp(i,j)=\max(dp(i-1,j),dp(i,j-1),dp(i-1,j-1)+[s_i==t_j])\)。
注意到\(s\)很短，于是显然考虑扫\(j\)，然后每次只记录所有\(dp(i,j)\)的情况。有一个经典结论是\(dp(i,j)-dp(i-1,j)\leq 1\)，于是我们记录所有的\(dp(i,j)-dp(i-1,j)\)，转移就强行预处理转移到哪。然后就做完了，复杂度也许是\(O(2^nnm)\)，不过那不重要了。
tjoi2018 游园会
跟这个一样做。
爆炸oj3591 最长上升子序列
给一个序列，求有多少种长\(n\)的排列的lis是这个序列。\(n\leq 15\)，保证答案不爆int。
考虑我们怎么求一个序列的lis来着，看起来是\(dp(i)\)表示\(i\)结尾的lis长度，然后\(dp(i)=1+\max\limits_{j<i,p_j<p_i}dp(j)\)。但是这个状态看起来很是不好压。
考虑还有一个牛逼做法求一个序列的lis，就是那个牛逼贪心求最小lds划分。这个过程中主要是要维护若干个集合，考虑我们压一下每个数是不是某个集合最小的数(或者它压根没有被扫到)，然后转移就强行预处理转移到哪。然后就做完了，复杂度也许是\(O(3^nn)\)，不过那不重要了。
uer#4 量子态的棋盘
注意到\(k\)巨大，先考虑怎么快速计算一个棋盘。注意到一个网格，如果知道有多少个球冲进来，那么由于球出去的方向和进来的方向和顺序无关，两个方向分别有多少球出去是很好算的。如果这个格子权值为\(1\)，有\(x\)个进来，那么就有\(\lceil\frac{x}{2}\rceil\)个从右边出去，\(\lfloor\frac{x}{2}\rfloor\)个从下边出去。
然后考虑要想用dp of dp，我们存一个巨大的球数量是不行的。考虑必然有\(\lfloor\frac{x}{2}\rfloor\)个从右边出去，\(\lfloor\frac{x}{2}\rfloor\)个从下边出去，只有最多一个还不确定，于是我们把这一个记入状态，轮廓线dp就好了。