|
可能并不简单
感谢 C202044zxy 学长精心准备的课件与精彩的讲解 。
治疗计划
- 注意 dp 的维度意识
- 我们本能地以时间为维度进行 dp ，然而难以为继
- 从规划前缀这一维度入手，
d
p
i
dp_i
dpi? 表示将
[
1
,
r
i
]
[1,r_i]
[1,ri?] 的人全部治愈的最小花费
- 我们本能地按
r
i
r_i
ri? 排序，对于
j
<
i
j<i
j<i 的情况，按照
T
i
<
T
j
T_i<T_j
Ti?<Tj? 和
T
i
>
T
j
T_i>T_j
Ti?>Tj? 分类讨论可以得到一个很合理的转移式：
-
d
p
i
=
d
p
j
+
c
i
(
r
j
?
l
i
+
1
≥
∣
T
i
?
T
j
∣
)
dp_i=dp_j+c_i(r_j-l_i+1\geq |T_i-T_j|)
dpi?=dpj?+ci?(rj??li?+1≥∣Ti??Tj?∣)
- 这样
O
(
n
2
)
O(n^2)
O(n2) 的
d
p
dp
dp 会得到 0pts 的好成绩 ！
- 原因在于我们没有意识到
j
>
i
j>i
j>i 时也能转移，画图表明其转移式毋宁相同
- 所以 dp 阶段并不显然，因为可能出现曲线救国（时间在起影响）
- 分析转移方程的特殊性质，想到最短路优化（拆绝对值的trick就不说了）
- 时间复杂度 O(mlogm) （为出题人点赞！）
Lanterns
这题也好难啊- 本题难在状态设计
我会套路！ - 最基本的状态为
d
p
i
,
j
dp_{i,j}
dpi,j? 表示处理完
[
1
,
i
]
[1,i]
[1,i] 的灯笼后最长前缀为
j
j
j 是否可行
- 这样状态数
O
(
n
2
)
O(n^2)
O(n2)
- 问题在于我们没有意识到 dp 值也能用来描述维度
- 设
d
p
i
dp_i
dpi? 表示处理完
[
1
,
i
]
[1,i]
[1,i] 的灯笼后能覆盖到的最长前缀
- 然后又是分类讨论 。注意抓子问题即可 。（咕咕咕
Favorite Game
- 确实是简单 dp ，但是 cf 评分 3300 一定不简单
- 这题涉及维度好多，但是富有经验的 oier
不包括我 会写出基本的 dp -
d
p
[
S
]
[
i
]
[
j
]
dp[S][i][j]
dp[S][i][j] 表示经过传送门集合为 S ，当前在地点 i ，做了 j 个任务的最少时间
- 这个看似很笨的 dp 其实包含了所有维度，时间复杂度
2
14
×
10
0
3
2^{14}\times 100^3
214×1003
- 如果在传送门，则不关心位置，如果在地标，则不关心时间
- 这启示我们对 dp 降维
- 设 f[S][i] 表示当前在传送门，完成 i 个任务的最小时间，g[S][i] 表示当前在第 i 个地标，完成的最大任务数 。
- 我们就能通过类似分类讨论的方法给 dp 降维 。 时间复杂度
2
14
×
10
0
2
2^{14}\times 100^2
214×1002
Group Projects
- 这题真的不难
但是我真的卡了好久 - 朴素做法是，dp[i][j][k] 表示前 i 个数，有 j 组没有最大值，最小值和为 k 的方案数
- 这样状态数
O
(
n
3
m
)
O(n^3m)
O(n3m)
原地爆炸 - 毋宁想到用
k
≤
1000
k\leq 1000
k≤1000 来优化
- 但是毋宁我的做法中 k 会远超过给定的 1000
- 也是合当该遭此劫， 竟然连一点 dp 技巧都没有积累到
- 我们假设 a[i] 是当前的最大值，算出此时的不和谐度之和，该维满足 <=1000
- 最终状态数
O
(
n
2
m
)
O(n^2m)
O(n2m)
|