前言

意思是处理未来信息和由过去推演未来的$DP$。

时间处理

和排序一样，在时间变换不影响正确性的情况下，我们会选择更优秀的方式处理，比如莫队的离散，$CDQ$分治，并查集的时间回溯等等。

再者，在部分题目中，时间成为了一个至关重要的组合部分，将时间视为信息、状态，是理所当然的。

综上所述，我得到了一个全新的思路，是否可以设计一个$DP$，更重要的，是设计一个和$DP$相关的思想，将时间作为集合、状态、属性、决策或划分依据，将时间总结并得到容斥、反演等重要的形式。

这个理念在我刷的某些高难度题上已经得到了验证，但想法还不算成熟，如果您愿意的话，请点赞关注，that is that。

未来DP 决策思想

预支付

将一组物品对未来的贡献提前，适用范围包括计算费用、预态平衡。

本质上，属于时间维度的区间运算，可以用数据结构维护。

值得注意的是，我们不能预支付不会被加入的物品。

换债款

将之前预支的贡献归还，与预支付对应，

本质上，属于时间维度的区间运算，可以用数据结构维护。

作为未来$DP$的逆操作而存在。

例题1. 甲虫

分析后效性，不同时间喝一滴水滴收获不同，暴力 $O(n^2m)$，

由于这是区间$DP$，$n^2$ 已经优化不了，考虑优化时间维度，这里先明确时间维度的趋向是 $min$，所以 $O(n^2)$ 的 $max$ 无法解决，不难想到广义$min-max$容斥，

如果将水看成物品，未被喝掉的水集体会在时间上产生贡献，但是水不一定都会加入，所以要枚举物品数量，即可解决。

如果动态知道物品时间上的费用和数量就可以用动态预支付。

上下界网络流

为了确保下界网络满流，我们要预支付，并在差网络还贷款。

未来概率DP

当要求我们对序列进行随机时，由于我们无法枚举所有方案，考虑未来概率$DP$，

也就是我们先确定物品，再用多决策$DP$求解问题。

由于之后的物品加入可以由之前的物品计算，但在一开始并没有一个顺序，这种人为指定物品（可能是多维的），提前算出未发生情况的贡献（方案数）的方法就是未来$DP$，而这类问题就叫做未来概率$DP$。

注意我们要有值确认的态，不然没法转移。

例题1. 波浪

我们不可能真的计算所有排列，所以人为定义顺序，将贡献改为插值计算。

然后，我们套用$DP$的思想，将其分组，设 $f_{i,j,k,l}$ 表示放完前 $i$ 个数、数列中存在 $j$ 个连通块（定义连通块为一段极长区间，满足这一段区间任意的相邻的两个数都被强制定为相邻，也就是说在之后的转移中，这一段区间内不能插入数）、数列总价值为 $k−5000$、有 $l$ 个边界已经与某个数强制相邻的方案数，讨论可以看题解。

由于求的是概率，答案为 $\frac{\sum\limits_{i=5000+M}^{10000} f_{N,1,i,2}}{n!}$

例题2. 线段树

显然枚举所有情况不可行，考虑未来$DP$，那怎么转移呢？

维护较小值，等价于连续较少值区间从左右端点开始缩小，如果是$01$序列的话，可以 $O(n^2q)$ 解决。

不难发现对于一般序列，我们也可以拆成$01$的形式，复杂度 $O(n^3q)$，统计每一个位置最终为 $0$ 的方案数。

可以发现，所有的 $dp$ 值的转移式子都完全一致，所以我们可以把所有初始值放到同一个 $dp$ 数组里面，然后进行一次整体的 $dp$，就可以求出答案。

具体地说$f(v,i,l,r)$实际对答案的贡献为$f(v,i,l,r)(val[v]-val[v+1])$

那么我们可以直接带着总贡献DP，也就是我们设$dp(i,l,r)=\sum_v f(v,i,l,r)(val[v]-val[v+1])$

实际的转移方程是不变的。

例题3. 随机数生成器

不难发现包含其他区间的区间对答案是没有影响的，这点与ZJOI线段树不同，

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

用容斥将难以计算的恰好为$i$转化为$\le i$。

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

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

我们不妨枚举 $j$ 表示有多少个数 $\le i$ ，那么 $h[i]$ 就等于：$g[j]×i^j×(x−i)^{n−j}$

区间覆盖即可。