全部评论
设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)。
留坑,考试结束发思路。
自己顶一顶!!!!!!!!!!!!!!!!!!!!
老铁,WAP笔试还没结束,直接贴问题出来真的好么(滑稽)
相关推荐
点赞 评论 收藏
分享
有礼貌的干饭人G了:校友直接投就好了,我简历上项目就只有一个原封不动的外卖也进了一家不错的独角兽
点赞 评论 收藏
分享
07-22 15:24
广西师范大学 大数据开发工程师 上周偶然刷到了lls的26秋招提前批开了,主包前段时间从字节实习完,秉持着投着试试的心态,认真填写了秋招的网申,提交成功的下一秒再刷新应聘页面,已经变成流程结束好夸张!是不是被机筛了,终究是双非不配了

点赞 评论 收藏
分享