会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
核心思路
本题是在显存预算约束下，选择若干中间层打 Checkpoint，使重计算总代价最小。相邻两个 Checkpoint（含隐式起点 0 与终点 N）之间的代价为
Cost(c,d)=k=c+1∑d−1forward_time[k−1]⋅(d−k)
可先用前缀和 S，由递推 Cost(c,d)=Cost(c,d−1)+(S[d−1]−S[c])、Cost(c,c+1)=0 在 O(N2) 内预处理全部区间代价。
