T6 午枫的陪伴时间 题目大意 有 nnn 个开始陪伴的时间，每次陪伴必续连续陪 ttt 天，期间不能进行别的陪伴的任务，如果陪伴需要花费 costcostcost 元，否则需要花费 valvalval 元，求最少花费。 解题思路 首先我们可以考虑按照 aia_iai 从小到大排序，然后考虑通过DP如何解决。 设 dpi,0dp_{i,0}dpi,0 表示前 iii 个选项，其中没选第 iii 项的最小花费； dpi,1dp_{i,1}dpi,1 表示前 iii 个选项，其中选择了第 iii 项的最小花费。 其中 dpi,0dp_{i,0}dpi,0 的状态转移很简单： dpi,0=min(dpi−1,0,dpi−1,1)+vidp_{i,0}=min(dp_{i-1,0},dp_{i-1,1})+v_idpi,0 =min(dpi−1,0 ,dpi−1,1 )+vi 。 令 sis_isi 为 viv_ivi 的前缀和，pospospos 为 iii 左侧第一个小于 ai−ma_i-mai −m 的下标。那么 dpi,1dp_{i,1}dpi,1 的状态转移为：dpi,1=min(dppos,0,dppos,1)+si−1−spos+costidp_{i,1}=min(dp_{pos,0},dp_{pos,1})+s_{i-1}-s_{pos}+cost_idpi,1 =min(dppos,0 ,dppos,1 )+si−1 −spos +costi 最后答案取 dpi,0dp_{i,0}dpi,0 和 dpi,1dp_{i,1}dpi,1 的最小值即可。 参考代码

以上是当时的代码。下面是分析。 努力观察得出状态转移方程：如果当前天数小于t，你只能选一天陪伴，因此第i天不选就要全盘收下dpi-1+vi，而某一天选了就不能选其他，要花费前面的v和ci 如果大于t，选第i个要找i-t以前的状态加上这个状态到i的v的总值的最优解，而不选第1个直接沿用以前的dp再加上vi 恭喜你喜提TLE。 累加vi可以看出要用前缀和，而找最小可以用优先队列优化。 O（nlogn）的复杂度

T6午枫的陪伴时间 * 官方辟谣 * 难度：普及+/提高 ？ * 思路分析 1. 准备阶段 输入 nnn 个选项的起始时间 aia_iai 计算总礼物成本 vvv（所有 viv_ivi 之和） 筛选出"可接受选项"（当 vi>costiv_i > cost_ivi >costi 时）： 结束时间em=ai+t−1e_m = a_i+t-1em =ai +t−1 节省金额sm=vi−costis_m= v_i - cost_ism =vi −costi 2. 区间排序： 对所有可接受选项按结束时间 eme_mem 进行升序 使用下表数组 ix[] 来保持原数组与排序后数组的关系 3. dp数组： 初始化：dp[1] =第一个区间的节省值 状态转移方程（递推是）： dp[i] = max(dp[i-1], s[i]+dp[j]) 4. 结算： 最优解 = 总礼物成本 v−v -v− 最大节省金额 dpmdp_mdpm 若无可接受选项 (m=0)(m=0)(m=0) ，直接输出总礼物成本 vvv * 通过代码 * 时间复杂度分析 O(n+m log m)O(n+m~log~m)O(n+m log m)