VMWARE propel oa 已跪

kaixinNI 发表于 2018-8-22 06:09
楼主我跟你一样，四十分钟这道题没做出来，后来查了一下用priority queue可以做

补充内容 (2018-8-22 06:1 ...

请问下priority queue怎么做啊？

可以对每一组数做一遍单调递增cost计算和单调递减cost计算 然后取cost小的值
单个单调递增只需要扫一遍list 扫到后数比前数小就计算差值 因为最小差值一定是该数和前数之差 前数减和后数加是一个道理 所以扫一遍就可以算出单调递增cost
复杂度O(2n)

littlegrasscao 发表于 2018-8-27 17:23
可以对每一组数做一遍单调递增cost计算和单调递减cost计算 然后取cost小的值
单个单调递增只需要扫一遍li ...

你这不对呀，想象一下第一个数是最大值的情况下，要想变成单调增那么所有后面的数都要加很大的数才行，这肯定不是解。

kevinchen9202 发表于 2018-8-23 07:25
挺常见的dp题。。

补充内容 (2018-8-23 07:38):

麻烦问下一维dp怎么解啊，谢谢！

动态规划，POJ有原题

katiechen94 发表于 2018-8-26 07:45
请问，用priority queue要怎么做？？

https://www.geeksforgeeks.org/mi ... ray-non-increasing/

我搜到的这个解法

wolf46 发表于 2018-8-27 11:27
请问下priority queue怎么做啊？

https://www.geeksforgeeks.org/mi ... ray-non-increasing/

搜到了这个解法，应该是一个意思

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

谢谢楼主大大

lZ是有收到HR的回信嘛？我什么都没收到～谢谢啦。