ABC E dp 思路 TLE,求优化
  • 板块学术版
  • 楼主M1saka16I72
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/3/16 22:04
  • 上次更新2024/3/17 08:23:24
查看原帖
ABC E dp 思路 TLE,求优化
422684
M1saka16I72楼主2024/3/16 22:04

设 fi,jf_{i,j} 为以第 ii 个数作为结尾,前面删除 jj 个数得到的最大价值,则转移方程为 max{fi−(j−x)−1,x}+vi(x≤j,ci−(j−x)−1≠ci)max\{f_{i-(j-x)-1,x}\}+v_i(x\leq j,c_{i-(j-x)-1}≠c_i),这样做是 O(nk2)\mathcal{O}(nk^2) 的,求教一下如何优化

2024/3/16 22:04
加载中...