Noip前的大抱佛脚----动态规划

2023-09-26 13:10:28

动态规划

有些问题：

求长度为\(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-A\sum k}f[fa]+\frac{1+A\sum b}{1-A\sum 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\)