EducationalDPContest社论

SoyTony 让我放歌词：

Wish You Were Gay

SoyTony 不让我放中文歌词，

《Wish You Were Gay》
Baby, I don’t feel so good
Six words you never understood
I’ll never let you go
Five words you never say (Aww)
I laugh alone like nothing’s wrong
Four days has never felt so long
If three’s a crowd and two was us
One slipped away (Hahahahahahahaha)
I just wanna make you feel okay
But all you do is look the other way
I can’t tell you how much I wish I didn’t wanna stay
I just kinda wish you were gay
Is there a reason we’re not through?

Is there a 12 step just for you?

Our conversation’s all in blue
11 “heys” (Hey, hey, hey, hey)
Ten fingers tearing out my hair
Nine times you never made it there
I ate alone at 7, you were six minutes away (Yay)
How am I supposed to make you feel okay
When all you do is walk the other way?

I can’t tell you how much I wish I didn’t wanna stay
I just kinda wish you were gay
To spare my pride
To give your lack of interest an explanation
Don’t say I’m not your type
Just say that I’m not your preferred sexual orientation
I’m so selfish
But you make me feel helpless, yeah
And I can’t stand another day
Stand another day
I just wanna make you feel okay
But all you do is look the other way
I can’t tell you how much I wish I didn’t wanna stay
I just kinda wish you were gay
I just kinda wish you were gay
I just kinda wish you were gay

看 SoyTony 整了”AtCoder dp 26 题”就来了 .

Educational DP Contest 是 AtCoder 的一个 DP 专题比赛，里面放了一些难度不高但是很有代表性的题目 .

标号 洛谷题号 题目名称 Tag Difficulty

Frog 1 线性 DP 1

Frog 2 线性 DP 1

Vacation 线性 DP 4

Knapsack 1 背包 DP 5

Knapsack 2 背包 DP 1

LCS 线性 DP 4

Longest Path 拓扑序 DP 1

Grid 1 坐标 DP 9

Coins 概率 DP 1

Sushi 期望 DP 9

Stones 线性 DP 8

Deque 区间 DP 1

Candies 线性 DP & 前缀和优化 0

Slimes 区间 DP 1

Matching 状压 DP 1

Independent Set 树形 DP 4

Flowers 线性 DP & 线段树优化 5

Walk 线性 DP & 矩阵快速幂优化 1

Digit Sum 数位 DP 4

Permutation 排列 DP 1

Grouping 状压 DP 9

Subtree 换根 DP 1

Intervals 线性 DP & 线段树优化 9

Tower 背包 DP & 贪心 8

Grid 2 坐标 DP & 容斥原理 1

Frog 3 线性 DP & 斜率优化 0

看 SoyTony 那个才想起来「坐标 DP」这个魔怔名字 .

TOC

A. Frog 1

令 (dp_i) 表示到第 (i) 块石头的最小代价，则

[dp_i=\min{dp_{i-1}+|h_i-h_{i-1}|,dp_{i-2}+|h_i-h_{i-2}|} ]

时间复杂度 (O(n)) .

B. Frog 2

类似 Frog 1，令 (dp_i) 表示到第 (i) 块石头的最小代价，则

[dp_i=\min_{j\le k}{dp_{i-j}+|h_i-h_{i-j}|} ]

时间复杂度 (O(n)) .

C. Vacation

令 (dp_{i,0/1/2}) 表示第 (i) 天进行游泳 / 捉虫 / 写作业的最大收益，则

[dp_{i,r}=\max_{r’\neq r}{dp_{i-1,r’}}+v_{r,i} ]

(v_r) 是 (r) 事件对应幸福值 .

时间复杂度 (O(n)) .

D. Knapsack 1

经典 01 背包，令 (dp_{i,j}) 表示物品 (1\dots i) 产生的质量和为 (j) 的最大价值和，则

[dp_{i,j}=\max{dp_{i-1,j},dp_{i-1,j-w_i}+v_i} ]

由于第 (i) 维只和第 (i-1) 维有关，于是可以滚动数组 .

时间复杂度 (O(nm)) .

E. Knapsack 2

发现价值和重量的量级互换，于是考虑对价值做 01 背包 .

令 (dp_{i,j}) 表示物品 (1\dots i) 产生的价值和为 (j) 的最小重量，然后就是朴素 01 背包转移，最后枚举一下价值和看看最小的满足条件的是哪个就好了 .

时间复杂度 (O(n\sum v)) .

F. LCS

令 (dp_{i,j}) 表示 (s[1:i]) 与 (t[1:j]) 的 LCS 长度 .

于是有：

[dp_{i,j}=\begin{cases}0&i=0\lor j=0\dp_{i-1,j-1}+1&i,j>0\land s_i=t_j\\max{dp_{i,j-1}+dp_{i-1,j}}&i,j>0\land s_i\neq t_j\end{cases} ]

直接转移可以得到 LCS 长度，发现每次转移其实隐含了选取哪些位置，于是对于每个 DP 值记录一个转移点，从 ((n,m)) 往前跳到 ((1,1)) 即可 .

时间复杂度 (O(|s|\cdot|t|)) .

G. Longest Path

令 (dp_i) 为以结点 (i) 结尾的最长序列，则

[dp_u=\min_{v\to u}{dp_v}+1 ]

因为是 DAG，所以按拓扑序转移即可 .

时间复杂度 (O(n+m)) .

H. Grid 1

令 (dp_{i,j}) 表示 ((1,1)) 到 ((i,j)) 的路径数量，则：

[dp_{i,j}=\begin{cases}dp_{i-1,j}+dp_{i,j-1}&a_{i,j}=\texttt{.}\0&a_{i,j}=\texttt{#}\end{cases} ]

直接转移即可，时间复杂度 (O(nm)) .

此题更优做法见 Grid 2 .

I. Coins

令 (dp_{i,j}) 表示前 (i) 枚硬币有 (j) 枚正面向上的概率 .

[dp_{i,j}=\begin{cases}0&i

直接转移，时间复杂度 (O(nm)) .

J. Sushi

因为 (a_i\le 3)，所以令 (dp_{a,b,c,d}) 表示 0,1,2,3 分别有 (a,b,c,d) 个的方案数 .

于是可以轻易转移：

[dp_{a,b,c,d}=1+\dfrac andp_{a,b,c,d}+\dfrac bndp_{a-1,b+1,c,d}+\dfrac cndp_{a,b-1,c+1,d}+\dfrac dndp_{a,b,c+1,d-1} ]

然而 (O(n^4)) 过不去，注意到 (a+b+c+d=n)，于是可以去掉一维，这样是 (O(n^3))，就可以过了 .

K. Stones

令 (dp_i) 表示取 (i) 个石子先手是否必胜，则

[dp_i=\bigvee_{a_j\le i}\lnot\,dp_{i-a_j} ]

直接转移，时间复杂度 (O(nk)) .

L. Deque

类似一个 Minimax 搜索，令 (dp_{l,r}) 表示剩下下标为 ([l,r]) 的数时，先手能取得的最大分数差 .

则端点挪一位转移即可，讨论已经取走的数的奇偶性即可得到转移是 max 还是 min .

时间复杂度 (O(n^2)) .

P.S. 区间 DP 有一个黑魔法是倒序枚举左端点正序枚举右端点，这样就不用枚举长度了 .

M. Candies

令 (dp_{i,j}) 表示 (1\dots i) 放 (j) 个糖的方案数，则

[dp_{i,j}=\sum_{k\le a_i} dp_{i-1,j-k} ]

(dp_i) 只和 (dp_{i-1}) 的一段区间和有关，可以前缀和优化 .

时间复杂度 (O(nk)) .

N. Slimes

经典的最优二叉搜索树问题，俗称石子合并

令 (dp_{l,r}) 表示为区间 ([l,r]) 内的答案，则：

[dp_{l,r}=\max_{k\in[l,r)}{dp_{l,k}+dp_{k+1,r}}+\operatorname{sum}(l,r) ]

时间复杂度 (O(n^3)) .

O. Matching

状压，令 (dp_{i,S}) 表示左部点 (1\dots i) 匹配了右部点 (S) 的答案，则每次删一个匹配转移即可 .

发现这个是按 popcount 顺序转移的，可以预处理，也可以暴力 .

时间复杂度 (O(n2^n)) .

P. Independent Set

树上独立集计数，令 (dp_{u,0/1}) 表示 (u) 的子树中的答案，其中 (u) 选 / 不选，直接上转移：

[\begin{aligned}&dp_{u,0}=\prod_{v\in\operatorname{son}(u)}(dp_{v,0}+dp_{v,1})\&dp_{u,1}=\prod_{v\in\operatorname{son}(u)}dp_{v,0}\end{aligned} ]

直接 DFS 一遍即可，(O(n)) .

Q. Flowers

令以 (i) 结尾的最大权 LIS 为 (dp_i)，则

[dp_i=a_i+\max_{\substack{j

(j

R. Walk

考虑 DP，(dp_{u,v,k}) 为 (u\to v) 长度为 (k) 的路径 .

显而易见

[dp_{u,v,k}=\sum_{w=1}^mdp_{u,w,k-1}G_{w,v} ]

可以发现矩阵乘法形式：(dp_k=dp_{k-1}\cdot G) .

于是 (dp_k=G^k)，矩阵快速幂计算，(O(n^3\log k)) .

最后把所有 DP 值加起来即可 .

S. Digit Sum

数位 DP，令 (dp_{x,e}) 表示到第 (x) 位且目前数位和 (s\equiv e\pmod d)（(0\le e

复杂度 (O(d\lg k)) .

T. Permutation

平凡排列 DP？令 (dp_{i,j}) 表示处理到第 (i) 个数且有 (j) 个大于位置 (i) 放的数 .

顺推做法大概就是：如果 (p_{i+1}>p_i) 那么就有 (j) 种方案可以放在 (i+1)，(p_{i+1}

逆推一样就是把差分换成前缀和，好实现一点，(O(n^2)) .

第一维可以滚一下，空间复杂度就是 (O(n)) 的了 .

U. Grouping

朴素状压 DP，先来一个 (O(n^22^n)) 暴力干出来所有可能组的权值和，每次转移枚举一个自己排掉即可 .

时间复杂度 (O(n^22^n+3^n)) .

V. Subtree

首先随便钦定一个根染黑然后做树形 DP，令 (dp_u) 表示 (u) 子树内的方案数，则：

[dp_u=\prod_{v\in\operatorname{son}(u)}(dp_v+1) ]

可以 (O(n)) 解决 .

然后考虑换根，转移从略，注意逆元不一定存在所以要换成前后缀积 .

总时间复杂度 (O(n))，口胡平凡，写起来比较恶心 .

W. Intervals

把区间的贡献挂到右端点，令 (dp_{i,j}) 表示到第 (i) 个区间，前一个 1 放在 (j) 的答案 .

[dp_{i,j}=\begin{cases}\displaystyle\max_{k

朴素转移是 (O(n^2)) 的，无法通过 .

首先滚动数组，这样空间就是 (O(n)) 的了，然后考虑顺推，就只需要支持区间加区间（全局）min，线段树维护即可，时间复杂度 (O(n\log n)) .

X. Tower

发现难点在于定序 .

前面物品的总重量为 (W)，(i) 必须放在 (j) 前面，则：

[\begin{cases}W+w_j\le s_i\W+w_i>s_j\end{cases} ]

后面就是 (s_j

这个比较构成一个严格偏序，于是我们可以确定出物品的上下顺序 .

然后有序就好做了，做一个类似背包 DP 的东西就好了，不计排序时间复杂度 (O(n(W+S))) .

Y. Grid 2

先定序 .

令 (dp_i) 表示从 ((1,1)) 到 ((x_i,y_i))，中间不经过其他障碍的方案数，求答案只需令 ((h,w)) 为第 (n+1) 个障碍就可以了，于是有

[dp_i=\dbinom{x_i+y_i-2}{x_i-1}-\sum_{j=1}^{i-1}\dbinom{x_i-x_j+y_i-y_j}{x_i-x_j}dp_j ]

直接暴力算，(O(n^2)) .

Z. Frog 3

斜率优化快忘干净了……

不过这题还是非常板板的，令 (dp_i) 表示跳到第 (i) 个石头上的最小花费，则

[dp_i=\min_{j

斜率优化，用单调队列维护下凸壳即可，时间复杂度 (O(n)) .

Bonus：({h}) 不单调递增？

Original: https://www.cnblogs.com/CDOI-24374/p/16585583.html
Author: Jijidawang
Title: EducationalDPContest社论