Menu Sidebar
Menu

Archive: December 20, 2020

Make Sum Divisible by P

给一个数组nums和一个p, 求删去最小的子数组后的数字和可以整除p. let s = sum of nums, r = s mod p -> r = (s + p) mod p 因为我们知道presum可以用两个指针表示其中间隔的和. let (i, j) = indexs in presum where 0 <=i <= j <= presum.length. since r = (s + p) mod p, then r = (pre[j] – pre[i] + p) mod p 因为我们知道2sum中, […]

Maximum Height by Stacking Cuboids

给一些砖块的长宽高, 可以旋转, 问怎么摆放可以有最高的高度, 求高度. 这个题虽然可以旋转, 但是其实因为限制: 必须完全小于长宽高的砖块才能放到另一个砖块上边. 所以没有旋转没有任何意义. 通过排序, 找到最长的, 然后再通过排序找到最大的. 即可做dp. 设dp[i]是包含砖块i作为可用砖块的最佳规划方案. 那么dp[i] = max{dp[j], where j < i and (i,j) meet requirements} 这个是bottom-up.

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.