看到一个英文题,矩阵移硬币,有大佬指点下吗??跪求思路


全部评论
设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)。
点赞 回复 分享
发布于 2017-09-24 21:40
留坑,考试结束发思路。
点赞 回复 分享
发布于 2017-09-24 20:44
自己顶一顶!!!!!!!!!!!!!!!!!!!!
点赞 回复 分享
发布于 2017-09-24 20:32
老铁,WAP笔试还没结束,直接贴问题出来真的好么(滑稽)
点赞 回复 分享
发布于 2017-09-24 20:09

相关推荐

06-07 21:26
江南大学 C++
话不多说,直接上时间线和图片1.2024年10月底发offer,并签三方2.2025年5月底公司违约
从零开始的转码生活:希望所有签了三方但直接违约的公司都倒闭!都倒闭!都倒闭!
点赞 评论 收藏
分享
06-05 19:46
已编辑
武汉大学 后端
点赞 评论 收藏
分享
05-07 17:58
门头沟学院 Java
wuwuwuoow:1.简历字体有些怪怪的,用啥写的? 2.Redis 一主二从为什么能解决双写一致性? 3.乐观锁指的是 SQL 层面的库存判断?比如 stock > 0。个人认为这种不算乐观锁,更像是乐观锁的思想,写 SQL 避免不了悲观锁的 4.奖项证书如果不是 ACM,说实话没什么必要写 5.逻辑过期时间为什么能解决缓存击穿问题?逻辑过期指的是什么 其实也没什么多大要改的。海投吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务