求此题变式的贪心做法证明或证伪
  • 板块P1220 关路灯
  • 楼主sjwhsss
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/12 17:19
  • 上次更新2024/11/12 20:23:16
查看原帖
求此题变式的贪心做法证明或证伪
982518
sjwhsss楼主2024/11/12 17:19

Rt，今天%\%拟赛做了这题的变式，只有时间（距离）限制但是没有功率限制，正解是斜率优化DP，我的赛时思路是 令 disi=∣posi−posc∣dis_i = |pos_i - pos_c| , 每个路灯无论如何总共会造成 sum=∑i=1ndisisum=\sum_{i=1}^{n}dis_i的贡献，然后看从出发点一直往右再左转和一直往左再右转对答案的贡献，取较小值，最后答案即

ans=sum+2×min⁡{dis1×(n−m),disn×(m−1)}ans=sum+2\times\min{\lbrace dis_1\times(n - m),dis_n\times(m - 1)\rbrace}

但是这样显然是错的，不过我赛时还是能拿50pts，老师给的一份贪心思路是先往一边走然后走到某个点后掉头往另一边走到底再回头走另一边答案就是

ans=sum+2×min⁡{(m−1)×disi+(disi+dis1)×(n−i),i≥m+1(n−m)×disi+(disi+disn)×(i−1),i≤m−1ans = sum + 2 \times \min \big\lbrace^{(n-m) \times dis_i +(dis_i+dis_n) \times (i - 1) ,i\le m-1}_{(m - 1) \times dis_i +(dis_i+dis_1) \times(n-i),i\ge m+1}

可以发现上面是下面的特殊情况，为什么这样就是对的，求证明或证伪

2024/11/12 17:19