A
定义 \(f_{i}\) 为跳到第 \(i\) 格的最小 cost。
跳出一步后的子问题和跳出一步前的子问题基本相同,只不过一个跳到 \(i-1\) 一个跳到 \(i\),则有
,其中 \(c_{i,j}\) 代表从 \(i\) 跳到 \(j\) 的 cost。
B
类似 A,不再分析。
\[f_i = \min\{f_{i-x} + c_{i-x, i} \mid x \in [1, k]\} \]C
定义 \(f_{i,j}\) 为第 \(i\) 天,这次的活动为 \(j\),最大的幸福。
\[f_{i,j} = \max\{f_{i-1,x} + h_{i,j} \mid x \ne j \} \]D
定义 \(f_{i,j}\) 为前 \(i\) 个物品达到 \(\le j\) 容量的最大价值。
\[f_{i,j} = \max\{f_{i-1, j-w_i}+v_i,f_{i-1,j}\} \]E
定义 \(f_{i,j}\) 为前 \(i\) 个物品达到 \(\ge j\) 容量的最小重量。
\[f_{i,j} = \min\{f_{i-1, j-v_i}+w_i,f_{i-1,j}\} \]F
定义 \(f_{i,j}\) 为第 \(S_{i..}\) 匹配 \(T_{j..}\) 的最大长度,有状态转移方程
\[f_{i,j} = \max\{f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+1 \text{ if } S_i = T_j\} \]得到 LCS 长度后,通过看转移方程的三项的哪一项与本格来判断通过哪路,来进行计算,即可解决。
G
设题面给出的图为 \(G\),建出反图 \(G'\),在 \(G\) 上跑 topsort,得到 \(A\),在 \(A\) 上进行 dp。
定义 \(f_i\) 为 \(1 \to i\) 的最长路的长度,有 \(f_i = \max\{f_x \mid x \in G'_i\} + 1\)
正确性证明:枚举的 \(x\) 就是一条边 \(x \to i\),在反图 \(G'\) 上表现为 \(i \to x\)
H
定义 \(f_{i,j}\) 为 \((1,1) \to (i,j)\) 的路径条数,则有
\(f_{i,j} = \left\{\begin{matrix}0 & m_{i,j} = \texttt{#} \\ f_{i-1,j} + f_{i,j-1} & \text{otherwise}\end{matrix}\right.\)
I
定义 \(f_{i,j}\) 为 \(i\) 个硬币投出 \(j\) 个正面的概率。
首先求出 \(f_{i,0} = f_{i-1,0} \times (1-p_i)\),然后有决策这个是正面还是反面,则有
。
J1
因为盘子的顺序不影响期望,所以直接把它压缩到 \(4\) 维,\(f_{w_0,w_1,w_2,w_3}\) 代表有 \(w_i\) 盘 \(i\) 个($i \in [0,3]),状态转移为
\[f_{w_0,w_1,w_2,w_3} = (1-\dfrac{w_0}{n}) \times (1+f_{w_0+1,w_1-1,w_2,w_3}\times\dfrac{w_1}{n}+f_{w_0,w_1+1,w_2-1,w_3}\times\dfrac{w_2}{n}+f_{w_0,w_1,w_2+1,w_3-1}\times\dfrac{w_3}{n}) \]J2
发现 \(w_0\) 几乎没用,而且 \(1-\dfrac{w_0}{n} = \dfrac{w_1+w_2+w_3}{n}\),于是可以直接缩掉这一维 dp。
K
定义 \(f_i\) 为有 \(i\) 个石子的时候谁赢。
先手具有游戏控制权,所以只要有一种取石子的方案使得取完石子是轮到谁谁输的方案(此时轮到后手),则先手赢。
可以定义 \(0\) 为轮到谁谁赢,\(1\) 为轮到谁谁输(\(\lor\) 为逻辑或,\(\lnot\) 为逻辑非),则有
。
L
注意到 \(X+Y\) 是定值,而 \(X-Y=X+Y-2Y\),也就是说 最大化 \(X-Y\) 就是最小化 \(Y\),最小化 \(X-Y\) 就是最大化 \(Y\)。
而左右出队相当于区间 \(L\) 左移或 \(R\) 右移,所以考虑区间 dp。
\(f_{L,R,s}\) 代表了 \([L,R]\) 区间内轮到 \(s\) 的最优 \(Y\)(最优就是 \(s\) 对应的最大/最小)。
只统计 \(Y\) 的分数,就可以 DP 了。
M1
定义 $f_{i,j} = $ 前 \(i\) 人一共 \(j\) 个蜡烛的方案数,则有
\[f_{i,j} = \sum_{g=0}^{\min(j,a_i)} f_{i-1,j-g} \]。
M2
发现转移出的 \(f_{i-1,[j, j-\min(j,a_i)]}\) 是一个区间,可以直接使用前缀和进行优化,定义
\[s_{i,j} = \sum^j_{k=0} f_{i,k} \],则有
\[f_{i,j} = s_{i-1,j} - s_{i-1,j-\min(j,a_i)-1} \]。
N
将 \([l,r]\) 合并成一块可以分裂为 \([l,m]\) 和 \([m+1,r]\) 做一次合并操作,于是定义 \(f_{i,j} = [i, j]\) 合并成一块的最小代价,且本次的代价一定是 \(\sum a_{[i,j]]\),则有
\[f_{l,r} = \min\limits_{m=l+1}^{r-1} f_{l,m} + f_{m+1, r} + \sum a_{[l,r]} \]。
O
定义 \(f_S\) 为 \(S\) 这个集合里面的所有人配对的方案数,则有
\[f_S = \sum f_{S - \{x\}} : x \in S \wedge a_{|S|,x} \]。
P
定义 \(f_x\) 为 \(x\) 是黑色的可能总数,\(g_x\) 为 \(x\) 是白色的可能总数。
\[f_x = \prod g_y : y \in S_x; g_x = \prod (f_y + g_y) : y \in S_x \]。
Q1
定义 \(f_i\) 为前 \(i\) 朵花满足条件的 max beauty,有
\[f_i = \max\limits_{j=1}^{i-1}\{f_j : h_j < h_i\} \]。
Q2
发现有 \(j<i \wedge h_i<h_j\),考虑一个数组,其下标为 \(h\),值为 \(a\),问题转化为单点修改,前缀 \(\max\),可以使用树状数组解决。
R1
暴力 DP,定义 \(f_{i,L,R}\) 为走了 \(i\) 步,\(L \to R\) 的路径总数,像 G 一样建出返图 \(G'\),得到
\[f_{i,L,R} = \sum (f_{i-1,L,x} : x \in G_R') \]R2
把上面的柿子换个写法,令邻接矩阵为 \(A\),则有
\[f_{i,L,R} = \sum f_{i-1,L,x} \times A_{x,R} \],构成矩阵乘法(\(f_{i} = f_{i-1} \times A\)),可以矩阵快速幂求 \(A^K\)。
S
定义 \(f_{i,j,k}\) 为 \([1,(j+1) \times 10^{i-1} - 1]\) 中有数位和 \(\bmod D = k\) 的数的数目,有
\[f_{i,j,k} = f_{i,j-1,k}\text{(开头不是 $j$)} + f_{i-1,9,k-j}\text{(开头是 $j$)}+ [j \bmod D = k]\text{(正好是 $j \times 10^{i-1}$)} \]T1
定义 \(f_{i,j}\) 为前 \(i\) 个数,最后一个数在排列中是第 \(j\) 小的方案数。
\[f_{i,j} = \left\{\begin{matrix}\sum\limits_{x=1}^{j-1} f_{i-1,x} & S_i = \texttt{<} \\ \sum\limits_{x=j}^{i} f_{i-1,x} & S_i = \texttt{>}\end{matrix}\right.\]T2
发现 T1 的状态转移构成区间和,所以考虑前缀和 dp。
U
定义 \(C_S = \dfrac 12\sum\limits_{x \in S} \sum\limits_{y \in S} a_{x,y}\),定义 \(f_S\) 为 \(S\) 划分出的最大收益,于是有
\[f_S = \max\{C_{T} + f_{S - T} \mid T \subseteq S\} \],预处理出所有的 \(C\) 就可以解决。