| PaintingFence | 您所在的位置：网站首页 › 刷漆刷几次 › PaintingFence |
PaintingFence
|
原题
假设，有n块连着的木板，每个木板的高度为h(h是0-5000内的随机值)，你需要把这n块木板上色，你手中的刷子宽度为1，每次上色你可以选择竖着刷完一块木板，或者横着刷连续的木板（但是不能跳跃空隙，一旦遇到空隙算这次横刷结束），问最少需要刷几次。 思路很容易能想到，如果某一列没有竖刷，那么必然被横刷，那么一定要从低处往高处都要横刷。 所以如果整个区域有横刷，那么高度最矮的那一列一定要被完全横刷掉。 此时，这个区域除掉这些被横刷的这几行，上面的部分被分成好多堆。每一堆的求解跟原问题是一样的，所以可以分治（递归）求解。 https://blog.csdn.net/liuxingwan/article/details/49183715 思路参考上面这个前辈，但是要额外注意下图这种情况，虽然我们以横着刷为更优解，但是还是会存在竖着刷更优的可能。所以，每次横刷生成的结果比较要跟竖着刷进行比较，也就是所谓的贪心算法。
代码是以这位前辈博客为蓝本做的修改，https://blog.csdn.net/y990041769/article/details/37935237 -- 基础思路是，先尝试横着刷，然后跟竖着刷进行比较，选择更优(小)的，需要注意的是，虽然使用的是Lua，为了保持统一性数组index依然从0开始插入 BoardLength = {} -- 存储木板的长度 tempTotalCount = 0 -- 用来临时存储结果值 -- 生成测试数据 BEGIN -- 测试数据 1 -- BoardMax = 3 -- 最多有多少木板 -- table.insert(BoardLength,0, 999) -- table.insert(BoardLength,1, 100) -- table.insert(BoardLength,2, 1000) -- table.insert(BoardLength,3, 10010) -- 测试数据 2 BoardMax = 5000 -- 最多有多少木板 for i = 1, BoardMax do table.insert(BoardLength,i-1,math.random( 100,5000 )) end -- 生成测试数据 END -- 注意，这里传入的时startIndex左闭endIndex右开参数 function solve(startIndex, endIndex) local shortest = 0x3f3f3f3f -- 0x3f3f3f3f 算法中常用的极大值，常用来标识无穷大，很有趣的一个用法。https://www.kawabangga.com/posts/1153 local longest = -1 for index = startIndex, endIndex - 1 do if BoardLength[index] > longest then -- 寻找最长的板子 longest = BoardLength[index] end if BoardLength[index] < shortest then -- 寻找最短的板子 shortest = BoardLength[index] end end -- 如果最长的和最短一样，说明全是齐的，直接返回横竖中的最小值 if longest == shortest then tempTotalCount = tempTotalCount + math.min(shortest, endIndex - startIndex) return end -- 无论后面是怎么刷的，为了保持分治的递归性，我们只认为刷掉了最短的那些连续块，所以这里只将最短的裁剪掉 for index = startIndex, endIndex - 1 do BoardLength[index] = BoardLength[index] - shortest end -- 这里的意思是，最短的长度和宽度比较，如果最短长度还大于宽度，那说明竖着刷才是最少的。当然如果这种情况，会有重复刷的部分。 local min = math.min(shortest, endIndex - startIndex) -- 将结果值更新到总结果值中 tempTotalCount = tempTotalCount + min for index = startIndex, endIndex - 1 do if BoardLength[index] > 0 then for subIndex = index, endIndex - 1 do -- 枚举index后面“连续”不为0段 -- 无法越空隙刷，所以一定要是连续的 if (BoardLength[subIndex] == 0 or subIndex == (endIndex - 1) and BoardLength[subIndex] > 0) then -- 最后一个可以是0，因为后面没有了，意味着可以连续刷完 subIndex = subIndex + 1; end local tempCount = tempTotalCount; -- 把这些连续的块，作为分治(递归)的分子，再进行处理 solve(index,subIndex); -- 整个算法中，每次分治时，板子数量确定了，竖着刷的次数其实确定的，那么我们先以横着刷为最优解，然后将横着刷跟竖着刷进行比较，再选取更优解。 -- 如果能一直保持最优解，那么我们认为得到的结果就是最优的，这里就是贪心算法的体现。 if tempTotalCount - tempCount > (subIndex-index) then --判断如果求得的值比直接一行一行刷更大的话，取更小的 tempTotalCount = tempCount + (subIndex-index); end -- 到这里说明这一个连续块执行完了，更新index以寻找下一个连续块 index = subIndex; break; end end end end solve(1, BoardMax) print(math.min(tempTotalCount, BoardMax))
|
【本文地址】
公司简介
联系我们