首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

照明系统设计(动态规划)- UVA 11400

You are given the task to design a lighting system for a huge conference hall. After doing a lot of calculation and sketching, you have figured out the requirements for an energy-efficient design that can properly illuminate the entire hall. According to your design, you need lamps of n different power ratings. For some strange current regulation method, all the lamps need to be fed with the same amount of current. So, each category of lamp has a corresponding voltage rating. Now, you know the number of lamps and cost of every single unit of lamp for each category. But the problem is, you are to buy equivalent voltage sources for all the lamp categories. You can buy a single voltage source for each category (Each source is capable of supplying to infinite number of lamps of its voltage rating.) and complete the design.

01

LeetCode笔记:121. Best Time to Buy and Sell Stock

这道题的意思就是,数组里的数按照顺序是每天的股票价格,你可以选择在某一天购买,然后再之后的某一天销售掉,销售的日子当然必须在购买的日子之后,也就是数组的顺序要靠后一些。要计算在哪两天进行买卖收益最大。这道题乍一看需要n*n的循环去计算每出一个价格后的最优解,我也是这样一开始就这样做,但是这样做时间复杂度太高,会超时,实际上也不用这么复杂。我们只需要每出一个新价格后,先判断这个价格减去我之前选择的买进价格后是否比之前的收益要大,以及这个新价格是否比我之前的买入价格要低,然后进行相应的操作即可,如果收益更大,就把这个收益记录下来,如果比买入价格低,就把买入价格换成这个价格。不需要担心这样直接换了之后往后计算的收益会不会不如之前,因为我们已经记录了在此之前的最大收益了,每次都会做对比的,而更换了更低的买入价格后,我们继续往后看能不能获得更大的收益,因为对于后面的数字来说这个数就是之前最小的买入价格了。其实想清楚后要进行的操作很简单,但如果想不清楚,就会觉得可能性太多了,要面面俱到总是会出问题,这里就要求头脑清晰了。

02
领券