这个屌丝很懒，什么也没留下！

codeforces 1700A Optimal Path 贪心_codeforce1700a

作者：IT小白 | 2024-02-09 18:06:14

codeforce1700a

说是贪心，想了一会，画个图辅助了解吧，我太菜了

如何证明蓝色格子的路线是最优解？只要证明红色线条的路线，可以不断地向右上方扭动身体，获得比原先路线更优的解。

比如8->13->14这个拐角，如果变成8->9->14，那么cost就变小了，这就符合了贪心。以此规则不停贪心，最终红色路线就优化到了蓝色路线。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/72553