动态规划

序列DP

有些问题：

求长度为(l)的上升子序列个数

形如一个值域的前缀和的形式，还要支持插入，所以可以用树状数组优化DP，(O(n^2logn))求解（[BZOJ4361]isn）
求最长上升子序列长度

两种做法，前者拓展性更强
- 设(f[i])表示到第(i)个位置的最长上升子序列长度，则(f[i]=max(f[j]+1),j<=i&&A[j]<A[i])，用值域树状数组优化前缀(max)即可
- 设(f[i])表示最长上升子序列长度为(i)的最小结尾值，可以知道(f)是单调递增的。新加入一个数(x)时找到大于等于(x)的第一个位置(j)，(f[j]=x)，意思是长度为(j)的最长上升子序列可以在(j-1)的基础上接(x)而不是接(f[j])，同时对其他的(f)不影响。如果(x)大于了最大值，(f)往后加一位
  
  如果求的是不降子序列那找到严格大于(x)的位置即可
关于最长上升子序列，有一个很神奇的性质：拥有双权值的序列，对其一维排序，对另一维做(LIS)答案相同

这个性质仿佛并没有什么用.....证明：对某一维排序并不影响两个元素间的二维偏序关系
序列为树的前序遍历，则为区间DP问题

考虑方向：

在点数很少的情况下可以进行状态压缩
点如果是没有区别的，可以采用拆分数进行更大数据范围的操作，再组合计数即可

(40)内的拆分数在(4W)以内

大概就是说状态可以回退，自己可以转移给自己或者自己之前的状态，这就需要高斯消元了

树上马尔可夫过程，(f[i]=Pf[fa]+(sum f[son])+1)

需要高斯消元但是时间不够，介绍一种 (O(n))的树上高斯消元

假设(f[i]=kf[fa]+b)，然后依次可以推导出(f[i]=frac{P}{1-Asum k}f[fa]+frac{1+Asum b}{1-Asum k})，从而表示这个表示可行，然后对于每个点算(k)和(b)就可以得到根的答案了

树的生成方式为：每次在当前的树的结构上随机选取一个点，在其下方挂上一个结点

已经遇到的题目：

问期望高度（10.17T2）

设(f[i][j])表示放了(i)个结点，高度不超过(j)的方案数，转移是(f[i][j]=f[k][j-1]+f[i-k][j])，表示为一棵树连到了另一棵树的根。最后除以阶乘即可。
问期望(sum_{i=1}^{n}sum_{j=1}^{n}dis(i,j))（HAOI2018苹果树）

考虑每一条边产生的贡献，枚举(i)点的(siz)，然后乘上(1-i)的生成方式、(i)子树的生成方式、其他地方的生成方式、以及i子树内选择编号的方案数

求(sum a^2)