[ZJOI2012] 波浪

定义 f(i,…)

考虑怎么推进，先拆开绝对值。

不难发现贡献只与i相关，这就好办了，

由于DP压缩了信息，所以我们不能动原来的数，所以考虑将原来看成填数，

然后怎么判断两段连成一段呢？

其实不用判断，只用累计相邻两个累计也就是联通块-1次即可。

因为我们算的是所用情况的贡献，而得出的状态联通块数-1是符合要求的。

设 $f_{i,j,k,l}$ 表示放完前 $i$ 个数、数列中存在 $j$ 个连通块、数列总价值为 $k−5000$、有l=0/1/2 个边界已经与某个数强制相邻的方案数。

其实这么做是很trick的，我们通过增加状态数量达到转换DP问题的目的，又通过对不需要计算的状态的压缩达到省略状态的目的。

[ZJOI2016] 线段树

定义 f(i,l,r,…) 显然 (l,r) 中的数相同最有讨论价值

因为有无用操作，记为 g(l,r)

形式化，有用操作一定是能被更新，所以套路地对有用情况有 [l,r]<=x 且 [l-1/r+1]>x

此时我们能算出所有方案数，对于具体值再记录是显然的。

有 f(i,l,r,v)

不难发现，直接统计会多次统计原数，所有统计增量即可。

P3600 随机数生成器

随机数。。。

min的存在让这道题并不好做。。

所以先套路化定义 f(i,…)

然后发现值域是有影响的，怎么消掉呢？

和之前的思路一样，维护方案数，因为概率$=$方案数$/$总方案数，期望$=$$\sum$概率*值。

维护概率，

因为维护最后的值的最大的概率等价于维护每个区间的最小值，

然后发现转换成 <= 可以少讨论很多东西。

然后可以思考总区间方案数，

当然这个可以转到一个个区间求。

有 $f[i][j]$ 表示前 $i$ 个位置放了 $j$ 个点且第 $i$ 个位置必须放点，覆盖所有左端点 $\le i$ 的区间的方案数。

也就相当于每个区间内都存在一个 $\le i$ 的数。

我们不妨枚举 $j$ 表示有多少个数 $\le i$，并令$g[j]$为使得每个区间至少包含一个点的方案数。 ，那么 $h[i]$ 就等于：$g[j]×i^j×(x−i)^{n−j}$

然后就可以了。

总结

多想，不行变换视角。