最大复合值思路求助

常规
,
1

老师讲的后面没听懂，求助（标签不用管）

2

dp

3

怎么dp

4

排序+dp

5

排序+dp，先确定顺序，然后可以定义一个函数简化操作，接着就可以dp转移了，注
意要初始化。

6

dp_{i,j} 表示前 i 个函数，从中选择 j 个来求那个表达式的最大值

7

然后呢

8

转移公式

for(i:1~n)//表示前 i 个函数
    for(j:min(k,i)~1)//表示从中取得个数(注意倒序，为了 dp)
        dp[j]=max(dp[j],/*这里是转移方程，填的东西如下/);

填：f_i(dp_{j-1})，题目里有

9

我教你

10

还有个排序，容易发现，若 f_i(f_j(1))>f_j(f_i(1))，则 i 函数在 j 函数前面，拆开就是后桌的代码

11

f_i(f_j(x)) 中由于 x 已知，所以这个式子的值只跟 a_i,a_j,b_i,b_j 有关，我们列出多项式 a_i\times a_j+a_i\times b_j+b_i 同样地，我们可以写出 f_j(f_i(x)) 的大小，跟 a_j\times a_i+a_j\times b_i+b_j 的大小有关，为了得到最优的函数顺序，如果 f_j(f_i()) 比 f_i(f_j()) 更优，那么我们需要将 f_j 放在 f_i 后面，所以 cmp 函数应该写成，若 a_j\times a_i+a_j\times b_i+b_j>a_i\times a_j+a_i\times b_j+b_i 则，返回 true，这样可以写出比较函数：

bool cmp(node x,node y){
    return y.a*x.a+y.a*x.b+y.b>x.a*y.a+x.a*y.b+x.b;
}
1 个赞
12

okk 写完题解了： 【智灵提高小班】模考 T4 - 常规 - 信友队论坛 (xinyoudui.com)

13

此话题已在最后回复的 15 天后被自动关闭。不再允许新回复。