本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-15 17:48:41

[ABC299F] Square Subsequence

考虑求 $S$ 中有多少种本质不同的子序列，需要保证 $f_i$ 不会同时转移到 $S_x=S_y$ 的 $x,y$ 才能避免算重。那么处理出 ${nxt}{i,c}$ 表示在 $[i+1,n]$ 中最小的 $j$ 使得 $S_j=c$， $f_i$ 只向 ${nxt}{i,c}$ 转移即可，也即 $f_{nxt_{i,c}}=f_{nxt_{i,c}}+f_i$，答案为 $\sum_{i=1}^n f_i$。

那么推广到前后出现两次的子序列数量，首先需要枚举断点 $r$，为了避免算重，定义 $r$ 为第一个子序列的结尾并枚举 $r$。每轮设 $f_{i,j}$ 表示第一个子序列结尾为 $i$，第二个子序列结尾为 $j$ 的方案数，初值 $f_{0,r}=1$。那么 $f_{nxt_{i,c},nxt_{j,c}}=f_{nxt_{i,c},nxt_{j,c}}+f_{i,j}$，其中 $f_{i,j}$ 的 $i\le r,j\le n$。每轮给答案累加上 $\sum_{i=r+1}^n f_{r,i}$ 即为答案。

[ABC320F] Fuel Round Trip

发现油箱容量 $H$ 跟 $n$ 同级，考虑设进状态。先考虑弱化版，也就是只需要从 $0$ 走到 $n$ 的最小代价。那么设 $f_{i,j}$ 表示走到 $i$ 且剩余油量为 $j$ 的最小代价，转移即可。

那么如果需要来回，就设 $f_{i,j,k}$ 表示到第 $i$ 个去时剩余油量为 $j$，返回时剩余油量为 $k$ 的最小代价。由于前后只能加一次油，所以需要同时考虑两次的加油情况，因此倒序枚举 $i$ 并转移即可。设 $dis$ 表示 $x_{i+1}-x_i$，$s_i$ 是题意中的 $F_i$，有如下转移：

• 不用：$f_{i,j,k}\leftarrow f_{i+1,j-dis,k+dis}$。
• 第一次用：$f_{i,j,k}\leftarrow f_{i+1,\min(H,j+s_i),k+dis}+p_i$。
• 第二次用：$k<H$ 时，$f_{i,j,k}\leftarrow f_{i+1,j-dis,k+dis-s_i}+p_i$；$k=H$ 时，$f_{i,j,k}\leftarrow f_{i+1,j-dis,l}+p_i$，其中 $l\in[H+dis-s_i,H]$。

另外要注意的是 $n-1$ 与 $n$ 之间要特殊处理初始状态，可以令 $s_0=H,p_0=0$，答案即为 $\min f_{0,0,i}$。

[ABC366F] Maximum Composition

考虑排好顺序以后 DP，需要有判断条件。考虑 $k$ 先后使用第 $i$ 和第 $j$ 个应该怎么排序，如果先使用第 $i$ 个，则最终为 $a_j(a_ik+b_i)+b_j$，先使用第 $j$ 个最终为 $a_i(a_jk+b_j)+b_i$，以此排序后设 $f_{i,j}$ 表示前 $i$ 个中使用 $j$ 个的最大收益即可。

同样的思路在 AT_DP_X 里也用到了，即先排号所有操作的顺序再进行 DP。