云计算(应老师要求来完成这篇TJ)

题目(虽然你们可能看不到)

首先,我们需要知道, 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!

3 个赞

666,比我写得好

2 个赞

哈哈,谢谢

1 个赞