题目中告诉了我们计算机的三个属性- -核心数量,闹钟频率和价格,我们要帮助 johnny 赚取最大利益,大家都知道 计算最大利益大概率与dp有关,所以,我们要用dp计算最大利益。
之后,我们要考虑一个问题- -如何将他们表示出来。当然,可以用集合表示当然可行,可数据范围太大了!用集合很容易爆,所以用数组是我们的不二之选
但随之又会引出一个问题–要用数组,我们就要把闹钟频率消掉。
大佬们肯定想到了题目中只 讲到了 他们的闹钟频率不少于f[j] 所以,我们可以使用排序算法!!
那… …是从小到大排序,还是从大到小排序呢?
- 从小到大
- 从大到小
0
投票人
很明显 当然是从大到小 虽然我一开始认为是从小到大
知道了这点以后 这题就不难了
我们可以列出以下的算式
:买入时-- f[i]=f[i-c[i]]-v[i]; 计算时从大到小更新
:卖出时-- f[i]=f[i+c[i]]+v[i]; 计算时从大到小更新
那么… …答案是什么呢?
(f从0开始)
是不是f[0]???
- 是f[0]
- 不是f[0]
0
投票人
首先,肯定不是f[0];
因为johnny可以买的和顾客需要的数量可能不相同
答案可能是f[0~sum] !
所以 我们需要将f 数组的初始化更改成–f[0]=0 ,其他f[1~不知多少]=-INF;
最后输出f数组中的最大值
蒟蒻de第一篇思路(不喜勿喷);