【做题记录】ABC-F-DP
KSCD_
·
·
个人记录
[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。