人何以配做世界的情种，为何动物却似生死无痛。
CF1874D Jellyfish and Miku
可能无法想象，但是现在的我甚至在 $a_i$ 确定的情况下都已经忘记了如何求期望。
先不考虑如何最小，看在 $a_i$ 确定时我们如何求期望。
根据期望的常见形式，我们一般考虑倒序，定义 $dp_i$ 表示从 $i\to n$ 的步数期望是多少。
故有转移式：$dp_i=\frac{a_{i}}{a_i+a_{i+1}}\times dp_{i-1}+\frac{a_{i+1}}{a_i+a_{i+1}}\times dp_{i+1}+1$。
然后我就不知道该怎么办了，反思一下为什么这么套路的东西都不会吧。
稍微让形式变得好看一点：$a_i\times (dp_i-dp_{i-1})=a_{i+1}\times (dp_{i+1}-dp_i)+(a_i+a_{i+1})$。
考虑常规换元思路：令 $g_i=dp_{i-1}-dp_i$，有 $a_{i+1}\times g_{i+1}=a_i\times g_i+(a_i+a_{i+1})$。（特别的，由 $dp_0=dp_1+1$，根据定义 $g_1=1$）。
回顾高中数学求通项的相关知识点，看一看我们能不能把 $g$ 的通项搞出来方便我们后面的运算：
转化一下形式，有 $g_{i+1}=\frac{a_i}{a_{i+1}}\times g_i+\frac{a_i}{a_{i+1}}+1$，迭代一下，发现本质上 $g_{i+1}=2\times \frac{\sum_{j=1}^i a_j}{a_{i+1}}+1$。
注意到我们要求 $dp_0$，有以下形式：
$$ \begin{aligned} dp_0&=\sum_{i=1}^n g_i\\ &=n+2\times \sum_{i=1}^n \frac{\sum_{j=1}^{i-1}a_j}{a_{i+1}} \end{aligned} $$ 考虑如何去最小化里面 $\sum_{i=1}^n \frac{\sum_{j=1}^{i-1}a_j}{a_{i+1}}$这个东西。这个就指向一个朴素 DP 的形式。
定义 $dp_{i,j}$ 表示确定了 $a_{x\in[1,i]},\sum_{k=1}^i a_k=j$，能得到的当前最小是多少。
显然有转移式：$dp_{i,j}=\min_{k=1}^j dp_{i-1,j-k}\times \frac{j - k}{k}$。
此时时间复杂度 $\mathcal{O}(nm^2)$。看起来也并不是特别好优化。（其实这里有一个决策单调，不过麻烦了点）
观察样例，我们或许可以得到一个比较普适性的提示：$a_i$ 单调不降。
思考一下这个东西的正确性，如果存在 $a_{i+1}<a_i$，发现交换两者，带回上式一定更优。
那么我们在枚举 $k$ 的时候显然有一个限制：$j+k\times (n-i)\le m$，发现此时复杂度就会来到调和级数 $\mathcal{O}(nm\ln m)$。
P6893 [ICPC 2014 WF] Buffed Buffet
注意到离散事物是容易的，将所有重量为 $w$ 的放在一起（对于一个食物把 $t_0-(i-1)\times \Delta t$ 都放进去），显然只有最大的 $\frac{W}{i}$ 是有效的，复杂度为调和级数：$\mathcal{O}(W^2\ln W)$。
考虑如何算连续食物。好了又不会了，感觉这几个凸壳合并很难办啊。
显然有贪心策略，一直吃收益最高的，直到当前收益与次高的相同。但是发现到了这里就不太好进行下去了。
考虑对于两种食物，$(t_0,\Delta t_1),(t_0,\Delta t_2),\Delta t_1\not= \Delta t_2$，考虑他们怎么样的比例吃最优：如果 $(t_0,\Delta t_i)$ 吃了 $w_i$ 的重量，那么显然在 $t_0-\Delta t_1\times w_1=t_0-\Delta t_2\times w_2$ 时最优。（类似于一个微元的思想，每次选瞬时收益更多的）此时得到的收益是：$t_0\times w_1-\frac{1}{2}\Delta t_1w_1^2+t_0\times w_2-\frac{1}{2}\Delta t_2 w_2^2$。
注意到 $\frac{w_1}{w_2}=\frac{\Delta t_2}{\Delta t_1}$。令 $w_1=k\times \Delta t_2,w_2=k\times \Delta t_1$。
带回收益：$t_0\times k\times (\Delta t_2+\Delta t_1)-\frac{1}{2}\Delta t_1k^2\Delta t_2^2-\frac{1}{2}\Delta t_2k^2\Delta t_1^2$
可以等效看作是对于食物 $(t_0,\frac{\Delta t_1\times \Delta {t_2}}{\Delta t_1+\Delta t_2})$，吃了 $k\times (\Delta t_1+\Delta t_2)$ 的重量。
也就是说，对于 $t_0$ 相同的两个食物，我们可以看作是一个的等效的食物 $(t_0,\frac{\Delta t_1\times \Delta {t_2}}{\Delta t_1+\Delta t_2})$。
那么回到我们的贪心策略，如果收益与次高的相同了，也就相当于当前 $t_0$ 相同了，那么可以将这两者进行等效合并，然后等到收益到后面和次次高相同，再进行合并，以此贪心。
注意到你要将离散食物和连续食物的重量和价值进行合并，所以算连续食物的复杂度应该是 $\mathcal{O}(nW)$。
发现可以通过，这个等效的思想还是很重要的。
P1721 [NOI2016] 国王饮水记
注意到只有 $>a_1$ 的才是有用的。
发现一个明显的贪心策略，即按大小排序之后，每次流水只会操作一段区间。
其实很好理解，因为很明显要把大小接近的放在一起才不会互相制约。（记住求平均数的时候要往这方面去想。）
那就很简单了，直接 DP 即可。
发现暴力 DP 是 $\mathcal{O}(n^3)$ 的，不太可过，继续挖掘性质。
发现从小到大排序之后，越往后我们选择的区间长度越小，因为越大的数我们必然希望他起到的作用更大。
感觉没什么用，不过我们猜测，长度大于 $1$ 的区间数不会很多。（面向数据编程得知最多只有 $14$ 个这样的区间）
那就很容易了，把长度为 $1$ 的放到最后一起，其他的在前面 DP，时间复杂度 $\mathcal{O}(14\times n^2)$。
告诉我们平均数的一些做题策略，以及当你发现单减的区间长度时，或许可以猜测长度为 $1$ 的区间会特别多。
P8864 「KDOI-03」序列变换
做不起，根本做不起，我就是官解中连第一个结论都没有想到的男人。
首先拿到这种，如果在原序列上的操作不好描述，那么考虑去求前缀或者后缀的值。
假设原数组的前缀异或数组为 $s_i=\oplus_{j=1}^i a_j$。发现一次对于 $i$ 的操作本质上就是交换 $s_i,s_{i-1}$。
考虑如何用 $s$ 去刻画至多 $k$ 个 $1$。先考虑 $k$ 是偶数的情况：我们钦定 $s_l=0$，其实就是 $s_l,..,s_r$ 中 $1$ 的连续段最多只有 $\frac{k}{2}$ 段。（反过来 $s_l=1$ 时，就是 $0$ 最多 $\frac{k}{2}$ 段）
有了操作和条件的刻画，考虑 DP。（一下我们都钦定 $s_l=0$，如果是 $1$ 反过来就好了。）
定义 $dp_{i,l,r}$ 表示将 $s_l,...s_r$ 分成 $i$ 个 $1$ 的连续段的最小操作次数是多少。
显然有：$dp_{i,l,r}=\min_{j=l}^{r-1} { dp_{i-1,l,j}+\text{val}\ _{j+1,r} }$，其中 $\text{val}_{j+1,r}$ 表示将这里面的 $1$ 放到一段的最小代价。
$\text{val}_{l,r}$ 的求解方法就是找到其中 $1$ 的位置的中位数，然后全部移过去即可，一个简单的贪心。
此时时间复杂度 $\mathcal{O}(n^3 \times k)$。
先考虑第一步优化，观察到我们可以把 $\text{val},dp_i$ 当作两个矩阵，注意到转移一定只能从 $dp_{i-1}\to dp_i$。
本质上是一个 $\min+$ 矩阵的卷积，可能下标并不是很对齐，可以将 $\text{val}_{j+1,r}$ 稍微移动到 $\text{val}_{j,r}$ 来对齐卷积的下标，那么显然满足结合律，可以使用矩阵快速幂优化做到 $\mathcal{O}(n^3\times \log k)$。
继续观察，发现这个转移式看起来非常符合正常的四边形不等式优化区间 DP 的形式。考虑感性证明，简单打个表发现确实满足四边形不等式的条件。
故考虑在卷积中，使用决策单调性优化卷积过程，将单次卷积从 $\mathcal{O}(n^3)\to \mathcal{O}(n^2)$。
那么总复杂度就来到了 $\mathcal{O}(n^2\times \log k)$。
当 $k$ 为奇数时，答案就是 $\text{ans}_{l,r}=\min_{i=l}^{r-1} dp_{l,i,\frac{k-1}{2}}+\text{val'}_{i+1,r}$，其中 $\text{val'}_{l,r}$ 表示将 $[l,r]$ 中的 $1$ 全部移到最右边的最小操作次数。显然，这一步也可以使用四边形不等式优化做到 $\mathcal{O}(n^2)$。
总时间复杂度 $\mathcal{O}(n^2\log k)$，代码一点也不好写。
