求贪心证明
  • 板块P2660 zzc 种田
  • 楼主401rk8
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/7/24 15:02
  • 上次更新2023/11/3 07:55:13
查看原帖
求贪心证明
236866
401rk8楼主2023/7/24 15:02

做法显然

每次覆盖最大的正方形显然是局部最优解,求证为什么也是全局最优

比如覆盖比最大正方形小一点的正方形,剩余部分的正方形可能变大,代价可能变小

由于类似 gcd⁡\gcd 的递归形式,很难直接计算两种情况的代价

2023/7/24 15:02
加载中...