看到一个英文题，矩阵移硬币，有大佬指点下吗？？跪求思路
2017-09-24 19:43 渣硕 Java
关注
全部评论
Leoric
南京理工大学 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）。
Leoric
南京理工大学 C++
留坑，考试结束发思路。
早起的蜗牛 楼主
楼主 渣硕 Java
自己顶一顶！！！！！！！！！！！！！！！！！！！！
Sakamoto
东北师范大学 C++
老铁，WAP笔试还没结束，直接贴问题出来真的好么（滑稽）
相关推荐
投递腾讯等公司10个岗位 点赞 评论 收藏
分享
07-01 22:55
兰州城市学院 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享