F |LIS| = 3
具体题面见上述链接
求长度为
n
n
n ，每个元素小于
m
m
m 的序列，满足以下条件的有多少种：
最长上升子序列长度为3.
考虑动态规划
我们需要记录长度为1的最长上升子序列最后一个元素的最小值，以及长度为2和长度为3的最小值。
dp数组f[i][k1][k2][k3]
i 表示当前序列长度，k1 表示当前序列长度为1的最长上升序列的最后一个元素的最小值（其实就是序列的最小元素），k2 表示当前序列长度为2的最长上升子序列的最后一个元素的最小值，k3 则表示当前序列长度为3的最长上升子序列的最后一个元素的最小值。动态规划数组的值则表示满足当前的序列有几种。
接下来，考虑动态规划是如何转移的
一开始当长度为0时，k1,k2和k3的值是正无穷，在操作过程中 m + 1 就是无穷。
插入第一元素后，长度为1，第一个元素的值就是k1。
如果当前的序列长度为 i - 1
在末尾插入第 i 个元素 x ，如果 x
转移方程为
if(x<=k1)f[i][x][k2][k3]=(f[i-1][k1][k2][k3]+f[i][x][k2][k3])%mod;
else if(x<=k2)f[i][k1][x][k3]=(f[i-1][k1][k2][k3]+f[i][k1][x][k3])%mod;
else if(x<=k3)f[i][k1][k2][x]=(f[i][k1][k2][x]+f[i-1][k1][k2][k3])%mod;
由于m<10，分别枚举动态规划的数组每一维，效率也满足要求。
我的代码
