Leoric
2017-09-24 21:40 南京理工大学 C++
关注
设S( x1 ,x2 ,y1, y2)为操作后只有( x1 ,x2 ,y1, y2)区间内的硬币留下的最小步数， 令Xleft=x1, Xright=m-1-x2 Yup=y1, Ydown=n-1-y2 则S( x1 ,x2 ,y1, y2)=2（Xleft+Xright+Yup+Ydown）-max(Xleft , Xright)-max(Yup , Ydown) 然后求出所有区间 ( x1 ,x2 ,y1, y2)硬币数为k的S，并取最小值。 求某个区间的硬币数量可以利用动态规划，预处理后每次求都是O(1)的复杂度。 枚举y1 y2 x1，则x2为满足硬币数不多于k的最大值。 所以总复杂度为O（n^2*m）。
查看原帖
点赞 1
相关推荐
投递美团等公司10个岗位 点赞 评论 收藏
分享
10-12 19:23
重庆邮电大学 Java 
敢逐云霄志：你打招呼语怎么能这么长，hr都没看下去的欲望，简明扼要说重点，就读于某某学校某某专业，26届应届毕业生，学信网可查，先后在某某公司实习过（如有），然后做过什么项目，想找一份什么样的工作，可实习几个月以上，期待您的回复。 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 校招生月薪1W算什么水平 #
33883次浏览 188人参与
# 哪一瞬间觉得自己长大了 #
38153次浏览 493人参与
# “vivo”个offer #
38688次浏览 280人参与
# 我是面试官，请用一句话让我破防 #
26472次浏览 128人参与
# vivo工作体验 #
27843次浏览 124人参与
# 如果上班像打游戏，你最想解锁什么技能 #
8069次浏览 70人参与
# 工作后明白的那些道理 #
21653次浏览 225人参与
# 一人一个landing小技巧 #
123800次浏览 1441人参与
# 实习最想跑路的瞬间 #
87382次浏览 542人参与
# 中美关税战对我们有哪些影响 #
42884次浏览 361人参与
# 机械制造2023笔面经 #
149481次浏览 840人参与
# 如果重来一次你还会读研吗 #
201537次浏览 1932人参与
# AI时代，哪些岗位最容易被淘汰 #
3276次浏览 27人参与
# 中美关系回暖，你会选择出海吗？ #
6569次浏览 107人参与
# 华为保温 #
107532次浏览 407人参与
# 哪些行业值得去? #
5276次浏览 50人参与
# i人适合做什么工作 #
11310次浏览 97人参与
# 美团开奖 #
221749次浏览 1146人参与
# 读研or工作，哪个性价比更高？ #
78166次浏览 768人参与
# 如果秋招能重来，我会____ #
37268次浏览 299人参与
# 华为池子有多大 #
110454次浏览 750人参与