这个题目中告诉了我们计算机的三个属性 核心数量,时钟频率和价格,我们要帮助 johnny 赚取最大利益,大家都知道 计算最大利益大概率与动态归划(dp)有关,所以,我们要用dp计算最大利益。
但随之又会引出一个问题–要用数组,我们就要把时钟频率消掉。
所以我们可以使用sort排序先给输入的数据按时钟频率从大到小排一下序,来减小时间复杂度
知道了这点以后 这题就不难了
我们可以列出以下的转移方程
买入时:f[i]=f[i-c[i]]-v[i];
卖出时: f[i]=f[i+c[i]]+v[i];
两者计算时均从大到小更新;
那么该从开始何结束呐?
答案
首先,肯定不是f[0]到f[n];
如果你是的恭喜你蛙了哦=)
因为电脑数可能与订单数并不相等
答案可能是f[0~sum] !
所以 我们需要将f 数组的初始化更改成–f[0]=0 ,其他f[1~???]=-INT MAX;
最后的最后
那个……
那个……
那个……
那个……
那个……
那个……
那个……
那个……
那个……
那个……
那个……
那个……
那个……
那个……
那个……
那个……
我好像是把李**的背下来了?反正改了吗=(