首页 > wyh的问题
开通博客写题解
头像 cheese_case
发表于 2022-01-10 17:26:46
本题与普通区间dp有一些区别，下面我悉数道来 首先决策：每次一次的决策（往左或者往右走），发现其一定是一个连续区间关闭； 关于本题与常规区间dp的区别：完成一个区间时最优解一定停在区间两端，而从小区间推至大区间的过程，要考虑距离成本 故小区间所停在的左右端点不同对后续造成影响，故要将其纳入状态； 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 流锡
发表于 2021-10-14 20:14:27
思路： 区间dp 设dp[l][r]表示[l,r]区间人在左端点里最小的耗电值 dp[r][l]表示[l,r]区间人在右端点的最小值 设起点为st 因为l<=st,r>=st所以这样设置dp不会有重叠的情况 然后就推方程啦 先用前缀和记录前i个电灯的每秒耗电量 同时可以注意到人在左端点的 展开全文
去ta的博客 赞 (3) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”