首先,我们需要知道, C_i 表示的是数量,而 V_i 表示的则是价格, F_i 表示的是时钟频率。
接下来,我们需要通过 F_i 来排序,那么,是好的放在前面,还是差的放在前面呢?
因为他有买和卖两个环节,我们需要分开讨论。
卖的时候,为了保证性价比,我们肯定需要把差的放在前面,好的放在后面。
买的时候,我们自然就是把好的放在前面了。
知道了以上信息后,我们需要一个数组 D ,用来干什么呢?当然是用来表示手中有 i 个核心了。
然后,我们使 D_0 = 0 ,其他的 D_{1-...} = -INF ,这样可以计算最大值。
买的时候,我们是从大到小排;卖的时候,我们是从小到大排。
因为买的时候我们的核心数量是增加的,所以, D_i = D_{i+C_i} - V_i 。
我们会惊奇地发现,哇,这不就是01背包吗?
我们便可以推出,卖的时候,应该是 D_i = D_{i + C_i} + V_i 。
买:
for(int i=1;i<=n+m;i++)for(int j=0;j+a[i].c<=w;j++)f[j]=max(f[j],f[j+a[i].c]+a[i].v);
卖:
for(int i=1;i<=n+m;i++)
{
w+=a[i].c;
for(int j=w;j-a[i].c>=0;j--)f[j]=max(f[j],f[j-a[i].c]-a[i].v);
}
你可能会问:咦,为啥有结构体呢?当然是方便啦。
我们也可以在结构体中用个 bool 类型的变量来表示是买还是卖。
那么我们的 D 数组已经算好了,那么答案就是 D_0 吗?
当然不是,我们需要再用一个变量来表示 D 数组里面的最大值。
最后在输出这个变量我们就可以收获:
\color{green}Thanks\space \color{blue}for\space \color{purple}watching\color{darkred}\space!