您的位置: 首页 > 文章 > CPOJ 2018.10.19提高测试 垃圾机器人 (litter) CPOJ 2018.10.19提高测试 垃圾机器人 (litter) 分类: 文章 • 2024-08-11 17:56:59 考虑对每一条路径差分,以此计算每个点iii在每轮中第kkk个捡的贡献:costi,k=(1+4)ai          (k=1)costi,k=((k+1)2−k2)ai=(2k+1)ai          (k>1) cost_{i,k}=(1+4)a_i\;\;\;\;\;(k=1)\\ cost_{i,k}=((k+1)^2-k^2)a_i=(2k+1)a_i\;\;\;\;\;(k>1) costi,k=(1+4)ai(k=1)costi,k=((k+1)2−k2)ai=(2k+1)ai(k>1) 所以一个点在这一轮中越早捡贡献越少 所以枚举捡了ttt轮,最远的n−t+1∼nn-t+1\sim nn−t+1∼n个垃圾在这轮中第一个捡,以此类推 一开始想当然地用了dp,把一个区间里的垃圾放在同一轮里捡,而贪心是把一个区间里的垃圾放在每一轮的同一个捡Code