线段树的扩展之浅谈zkw线段树

posted on 2018-08-06 19:22:55 | under 线段树 | 29

思路：将一颗大树分为若干子树，枚举每个子树

• 如何分割一棵树

1. 利用中序遍历

   例如 P1040 [NOIP2003 提高组] 加分二叉树，利用中序遍历，所有的左儿子都在根节点的左边，所有的右儿子都在根节点的右边，且所有的子树在遍历中都是连续的。 因此可以枚举区间长度，再枚举起点和根节点。此外，应默认子树都没有左子树，否则一定不是最优解。

找最优子结构

对乘积A1A2…An的任意加括号方法都会将序列在某个地方分成两部分，也就是最后一次乘法计算的地方，我们将这个位置记为k，也就是说首先计算A1…Ak和Ak+1…An，然后再将这两部分的结果相乘。 最优子结构如下：假设A1A2…An的一个最优加括号把乘积在Ak和Ak+1间分开，则前缀子链A1…Ak的加括号方式必定为A1…Ak的一个最优加括号，后缀子链同理。 一开始并不知道k的确切位置，需要遍历所有位置以保证找到合适的k来分割乘积。

最优值

将矩阵连乘积$Ai,Ai+1……Aj$记为A[i：j]。对于矩阵连乘积的最优计算次序的问题，设计算A[i：j]，1<=i<=j<=n,所需要的最小数乘次数为m[i][j]，则原问题的最优值为m[1][n]。 当i=j时，A[i：j]=Ai为单一的矩阵，则无需计算，所以$m[i][j]=0，i=j=1，2，……，n$。即对应的二维表对角线上的值全为0。当i<j时，这就需要用步骤（1）的最优子结构性质来计算m[i][j]。若计算A[i:j]的最优次序在Ak和Ak+1之间断开，$i<=k<j$,则 ${m[i][j]m[i][k]+m[k+1][j]+p_{i-1}*pk*pj}$ k的位置只有 $j-i$ 种可能，即k属于集合${i,i+1,……,j-1}$，所以k是这j-i个位置中使计算量达到最小的那个位置。所以m[i][j]可以递归地定义为 $m[i][j]={min{m[i][k]+m[k+1][j]+p_{i-1}*pk*pj}i<j ,i<=k<j}$ 将对应于m[i][j]的断开位置k记为s[i][j]，在计算出最优值m[i][j]后，可递归地由s[i][j]构造出相应的最优解

原理

因为操场是个环，将环展开到n+n的数组里，同时也把a复制一份

s求前缀和，用于在calc函数中求出从i到j堆石子的个数和

dpmax和dpmin字面意思，存在合并i到j堆后的最大值/最小值

a存输入数据

1. 找到满足 $q_{k-1} \lt q_{k+1}$ 的最小下标 $k$
2. 找到满足 $q_{j-1} \gt q_{k-1} + q_k$ 的最大 $j \lt k$
3. 从列表中清除 $q_{k-1}, q_k$
4. 在 $q_{j-1}$ 之后插入 $q_{k-1} + q_k$
5. $q_{-1}$ 和 $q_{n+1}$可以用 $\infty$ 处理