CF1785D Wooden Spoon
为了方便，将题目中的大小关系反转一下。
这是一个 \(n+1\) 层的满二叉树，第 \(i\) 层每个点都是 \(2^{n-i+1}\) 个人中的胜者。
如果从下往上 dp，需要记录胜利者编号和得到木勺者编号，会爆掉。
那么从上往下 dp。设 \(dp_{i,j}\) 表示第 \(i\) 层 \(j\) 胜利随即一直失败的方案数。
转移方程
\[dp_{i+1,k}=\sum_{j>k}2\times dp_{i,j}\times\binom{j-2^{n-i}-1}{2^{n-i}-1}\times2^{n-1}! \]前缀和优化后复杂度 \(O(n2^n)\)
CF809D Hitchhiking in the Baltic States
设 \(dp_i\) 表示长度为 \(i\) 的上升子序列最后一个数的最小值。
转移方程很简单，假设当前限制区间为 \([l,r]\)：
\[dp_i=\left\{\begin{matrix} \begin{aligned} &\min(dp_i,l)&&dp_{i-1}<l\\ &dp_{i-1}+1&&l\le dp_{i-1}<r\\ &dp_i&&dp_{i-1}\ge r \end{aligned} \end{matrix}\right. \]暴力转移是 \(O(n^2)\) 的，可以用平衡树优化。
- 对于第一种情况，找到最大的小于 \(l\) 的数转移。
- 对于第二种情况，将 \([l,r)\) 内的数向右移一个位置并 \(+1\)。但其实并不需要真的移，第一种情况的时候已经在 \(l\) 前插入了一个数。
- 对于第三种情况，将第一个不小于 \(r\) 的数删掉。
时间复杂度 \(O(n\log n)\)。
P5044 [IOI2018] meetings 会议
很容易想到，可以找到一个区间内的最大值将其分为两个独立的区间求解。暴力事件复杂度 \(O(nq)\)。
回想上面的过程，很像笛卡尔树，于是笛卡尔树。将问题区间先按类似上面的方法分成两个区间，这样他们的左右端点分别有一个是笛卡尔树上的点。
那么只需对笛卡尔树上的每一个点求出 \(f_{l,i}\) 表示从这个点代表区间的左端点到 \(i\) 这段区间的答案。
假设已经递归完 \(mid\) 的左右儿子，所以 \(f_{l,i}(l\le i<mid)\) 已经求出。不难想到 \(f_{l,mid}=f_{l,mid-1}+h_{mid}\)。又有转移方程：
\[f_{l,i}=\min(f_{l,mid}+(i-mid)\times h_{mid},f_{mid+1,i}+(mid-l+1)\times h_{mid}) \]暴力转移又是 \(O(n^2)\)。注意到取 min 的左边随 \(i\) 变化的增量为 \(h_{mid}\)，右边随 \(i\) 变化增量不超过 \(h_{mid}\)，故中间一定有一个分界线，之前取左边，之后取右边。用线段树维护当前答案，需要支持区间赋值一次函数，区间加，线段树上二分。
AGC012E Camel and Oases
转化一下问题，相当于有 \(\log V\) 层，每层有一些线段。每层选一条线段使得这些线段的并集为 \([1,n]\)，第一层选的线段固定。
考虑 \(dp\) 出两个信息。选了集合 \(s\) 中层数后覆盖的最长前缀和后缀。枚举第一层每条线段，答案易求。
标签：总结,笛卡尔,线段,练习,20230708,mid,times,区间,dp From： https://www.cnblogs.com/dks-and-xiao-yu/p/17537234.html