hiho一下第285周《Selling Antique Coins》题目分析

1
0

《Selling Antique Coins》题目分析

首先我们思考这样一个问题:假如你想把某几枚确定的硬币卖给VIP顾客,如何判断能否卖成功?

比如年份数组 A = [100, 200, 300, 400, 500, 600],R = 2,我们现在想把300和600年的硬币卖给顾客,能不能卖出去?

判断的方法是按如下贪心策略决定一种排列顺序:

(1) 我们首先把想卖的硬币按年份递增排序: 300和600

(2) 然后我们把第一枚想卖的放在最左边,然后选择R枚年份比它小的不想卖的放在第一枚左边 [300, 100, 200]

(3) 重复(2)的过程,按年份从小到大放入想卖的硬币,每放一枚想卖的就在其之后放R枚不想卖的年份比它小的。 [300, 100, 200, 600, 500, 400]

(4) 如果上述过程中,发生找不出R枚年份比它小的硬币这样的情况。那么就说明不存在排列方案能卖出去这些硬币。反之就能卖出去。

比如上面的例子中,我们就能排成[300, 100, 200, 600, 500, 400]这样把300年和600年的硬币卖出去。

如果我们还是A = [100, 200, 300, 400, 500, 600],R = 2,现在想卖400和500的。就会发现放了500之后找不出2个比500小的硬币:

[400, 300, 100, 500, 200, X]

所以400和500的组合是卖不出去的。

注意我们上述讨论的都是硬币的年份,而不是硬币的价格。

总结上面的贪心方案,我们可以得到一个很简洁的判断方法: 卖出的年份第i小的硬币,其年份在所有硬币中的排名需要大于等于i*(r+1)。

要注意上述方法不适用于卖出的年份最大的硬币。例如A = [100, 200, 300, 400], R = 2, 是可以卖出300和400的。因为放了400之后,[300, 200, 100, 400], 400右边没有位置就不用再放 2个比400小的硬币了。

有了上面简洁的判断方法,我们可以用DP解决最初的问题:

首先把硬币按年份从小到大排序。所以我们默认A = [A1, A2, ... AN]是按从小到大排序的。

然后我们用dp[i][j]表示前j个硬币卖出i个且第j枚硬币也卖出的最高价格。

dp[i][1..(r+1)*i-1] = -INF (不符合判定条件,即卖不出去)

令f[i][j] = max{dp[i][k] | k <= j} = max(dp[i][j], f[i][j-1]) 即前j枚中卖出i枚的最高价格。

则dp[i][j] = f[i-1][j-1] + price[j]

最后所有dp[i][j]的最大值就是答案

1 answer(s)

0

前面贪心的想法基本一样,不过如果不用dp,改用最小堆存放当前已选的硬币,时间复杂度大概O(NlogN),空间复杂度为O(N)

write answer 切换为英文 切换为中文


转发分享