dp 专题总结
题单： t h i s w a y s i r this\ way\ sir this way sir
来自于ATcoder的一次 dp 专题比赛。
Coins
设 f i , j f_{i,j} fi,j 为 考虑前 i i i 个硬币，正面向上的个数有 j j j 个 的概率。
有转移：
f
i
,
0
←
f
i
−
1
,
0
×
(
1
−
p
i
)
f
i
,
j
←
f
i
−
1
,
j
×
(
1
−
p
i
)
+
f
i
−
1
,
j
−
1
×
p
i
f_{i,0} \leftarrow f_{i - 1,0} \times (1 - p_i) \\ f_{i,j} \leftarrow f_{i - 1,j} \times (1 - p_i) + f_{i - 1,j - 1} \times p_i
fi,0←fi−1,0×(1−pi)fi,j←fi−1,j×(1−pi)+fi−1,j−1×pi
然后将 ∑ i = n / 2 + 1 n f n , i \sum_{i = n / 2 + 1}^n f_{n,i} ∑i=n/2+1nfn,i 输出即可。
Sushi
很轻松可以设出 f i , j , k , p f_{i,j,k,p} fi,j,k,p 盘子数量的四维状态，但题目只能开三维。
发现 i + j + k + p = n i + j + k + p = n i+j+k+p=n 所以用 n − j − k − p n - j - k - p n−j−k−p 来表示 i i i,
然后算概率就可以了。
Candies
设 f i , j f_{i,j} fi,j 为第 i i i 个人，用了 j j j 颗糖果。
有转移：
f
i
,
j
←
∑
k
=
j
−
a
[
i
]
j
f
i
−
1
,
k
f_{i,j} \leftarrow \sum_{k = j - a[i]}^{j} f_{i - 1,k}
fi,j←k=j−a[i]∑jfi−1,k
考虑前缀和优化。
f i , j ← s j − s j − a [ i ] − 1 f_{i,j} \leftarrow s_j - s_{j - a[i] - 1} fi,j←sj−sj−a[i]−1
Independent Set
树上 d p dp dp
求独立集， f x , 0 = ∏ y ∈ subtree x ( f y , 0 + f y , 1 ) , f x , 1 = ∏ y ∈ subtree x f y , 0 f_{x,0} = \prod_{y \in \operatorname{subtree}_x}(f_{y,0} + f_{y,1}),f_{x,1} = \prod_{y \in \operatorname{subtree}_x} f_{y,0} fx,0=∏y∈subtreex(fy,0+fy,1),fx,1=∏y∈subtreexfy,0
Flowers
最长上升子序列 的 BIT 优化。
Walk
矩阵快速幂即可。
Permutation
不考虑具体大小，只考虑相对大小，有转移：
f
i
=
{
∑
j
<
i
f
j
(
o
p
i
=
0
)
∑
j
>
i
n
f
j
(
o
p
i
=
1
)
f_{i} = \begin{cases} \sum_{j < i} f_{j} & (op_i = 0) \\ \sum_{j > i}^n f_{j} & (op_i = 1) \\ \end{cases}
fi={∑j<ifj∑j>infj(opi=0)(opi=1)
套上前缀和优化。
Grouping
先状压出每一个物品在连其他的物品可能产生的贡献。
然后状压出每种分组的值，最后将每个状态的值通过枚举子集求最优解。
Intervals
梦回天天爱打卡。
定义 f i f_i fi 为枚举到 i i i 时的答案。
有转移，
f
i
←
max
(
f
j
+
∑
j
≤
l
k
≤
i
≤
r
k
w
(
k
)
)
f_{i} \leftarrow \max(f_{j} + \sum_{j \leq l_k \leq i \leq r_k} w(k)) \\
fi←max(fj+j≤lk≤i≤rk∑w(k))
然后发现，我们优化不了。
考虑转换状态，定义 f i f_i fi 为枚举到 i i i 且 所有区间右端点 ≤ i \leq i ≤i 时的答案。
那么，我们只需要在转移时，遇到区间右端点时，在线段树上区间加上权值即可。
Tower
发现 s i − w j < s j − w i s_i - w_j < s_j - w_i si−wj<sj−wi 时，选择 j j j 显然更优。
变形 s i + w i < s j + w j s_i + w_i < s_j + w_j si+wi<sj+wj。
按 s i + w i s_i + w_i si+wi 排序，跑 01 01 01 背包
Frog 3
斜率优化板题
有转移:
f
i
=
max
j
<
i
(
f
j
+
(
h
i
−
h
j
)
2
+
c
)
f_{i} = \max_{j < i}(f_{j} + (h_i - h_j)^2 + c)
fi=j<imax(fj+(hi−hj)2+c)
对于最优决策点
j
j
j，有
f
i
=
f
j
+
(
h
i
2
−
2
h
i
h
j
+
h
j
2
)
+
c
f_{i} = f_j + (h_i^2 - 2h_ih_j + h_j^2) + c \\
fi=fj+(hi2−2hihj+hj2)+c
f
j
+
h
j
2
=
2
h
i
h
j
−
c
+
f
i
+
h
i
2
f_j + h_j^2 = 2h_ih_j - c + f_i + h_i^2
fj+hj2=2hihj−c+fi+hi2
那么， k = 2 h i , b = f i + h i 2 − c k = 2h_i,b = f_i + h_i^2 - c k=2hi,b=fi+hi2−c
h i h_i hi 单调，直接上单调队列。
Grid 2
定义 f i f_i fi 为 仅经过 ( x i , y i ) (x_i,y_i) (xi,yi) (此为障碍) 的所有路线。
有转移：
f
i
=
(
x
i
+
y
i
−
2
x
i
−
1
)
−
∑
j
<
i
f
j
(
x
i
−
x
j
+
y
i
−
y
j
x
i
−
x
j
)
f_i = \dbinom{x_i + y_i - 2}{x_i - 1} - \sum_{j < i} f_{j}\dbinom{x_i - x_j + y_i - y_j}{x_i - x_j}
fi=(xi−1xi+yi−2)−j<i∑fj(xi−xjxi−xj+yi−yj)
然后将 ( h , w ) (h,w) (h,w) 视为最后一个障碍， f n + 1 f_{n + 1} fn+1 就是答案。
标签：AtCoder,Contest,max,sum,leftarrow,leq,fi,dp From： https://blog.csdn.net/qq_49785217/article/details/143403647