WanderOvO
进化成更好的人
首页
归档
标签
关于
友链
搜索
文章目录
站点概览
WanderOvO
12
文章
6
标签
DP状态定义与转移方程大全
发布于
2025-12-17
|
标签:
经验
、
算法
|
2
分钟
|
238
字数
目标：
积累
50
50
5
0
到
100
100
1
0
0
道 DP 题的转移方程，然后通过人脑进行数据挖掘。
看到状态定义和转移，反推这个题目的限制要求或者要求的东西。
看到题目的限制，知道可能采用什么样的状态设计和转移技巧。
题目
数据范围
状态定义
状态转移
备注
GYM105845F
n
=
5000
n = 5000
n
=
5
0
0
0
d
p
[
i
]
[
j
]
dp[i][j]
d
p
[
i
]
[
j
]
为将前
i
i
i
个数分成
j
j
j
段的合法方案数
d
p
[
i
]
[
j
]
+
=
d
p
[
k
]
[
j
−
1
]
dp[i][j] += dp[k][j - 1]
d
p
[
i
]
[
j
]
+
=
d
p
[
k
]
[
j
−
1
]
，其中
(
s
[
i
]
−
s
[
k
]
)
≡
0
(
m
o
d
j
)
(s[i] - s[k]) \equiv 0 (mod\ j)
(
s
[
i
]
−
s
[
k
]
)
≡
0
(
m
o
d
j
)
，利用同余可以优化到
d
p
[
i
]
[
j
]
=
c
[
j
]
[
s
[
i
]
%
j
]
dp[i][j] = c[j][s[i] \% j]
d
p
[
i
]
[
j
]
=
c
[
j
]
[
s
[
i
]
%
j
]
，
c
[
j
+
1
]
[
s
[
i
]
%
(
j
+
1
)
]
+
=
d
p
[
i
]
[
j
]
c[j + 1][s[i] \% (j + 1)] += dp[i][j]
c
[
j
+
1
]
[
s
[
i
]
%
(
j
+
1
)
]
+
=
d
p
[
i
]
[
j
]
连续段DP
赞赏
x
感谢您的支持，我会继续努力的!
扫码打赏，你说多少就多少
