题目
link。
大致思路
看到这道题目我们想到使用 dp 来解决。
dp 要素
- dp 定义：我们定义 dp_{i,j} 表示在前 i 个函数中，选择 j 个函数，能得到的最大值。
- dp 初始化：当 j=0 时，我们不选择任何函数，以便后续函数中嵌套，所需要的乘法运算，我们将 dp_{i,0}=1\ (i\in [1,n])。
- dp 方向：我们使用两层循环，其中外循环，从 1 遍历到 n 枚举 i 的取值，内循环从 1 到 \min\left\{k,i \right\} 因为，我们选择的函数个数不能超过 k 个。
- dp 转移方程：有两种情况，选择当前函数与不选择当前函数，其中若选择当前函数，我们将得到的新的最大值为 a_i\times dp_{i-1,j-1}+b_i 所以，转移方程为 dp_{i,j}=\max\left\{dp_{i-1,j},a_i\times dp_{i-1,j-1}+b_i \right\}。
- dp 答案：我们设答案为 ans 则，对于每一个 i 我们都比较 ans 与 dp_{i,k} 的大小。
dp 伪代码
根据上述思路，我们写出伪代码：
/*初始化*/
for(/*遍历 i*/){
for(/*遍历 j*/){
//状态转移
}
//更新 ans
}
新的问题
当你将代码补全，提交上去后，你会得到 \color{red}{WA\ \ 90} 的成绩。
原来，是因为我们并没有考虑函数的顺序，这导致了可能得到的答案并不是最优解。
意思就是我们需要将函数排序。
我们考虑两个函数 \mathrm{f}_i 和 \mathrm{f}_j：\mathrm{f}_i(\mathrm{f}_j(x)) 中由于 x 已知，所以这个式子的值只跟 a_i,a_j,b_i,b_j 有关，我们列出多项式 a_i\times a_j+a_i\times b_j+b_i 同样地，我们可以写出 \mathrm{f}_j(\mathrm{f}_i(x)) 的大小，跟 a_j\times a_i+a_j\times b_i+b_j 的大小有关，为了得到最优的函数顺序，如果 \mathrm{f}_j(\mathrm{f}_i()) 比 \mathrm{f}_i(\mathrm{f}_j()) 更优，那么我们需要将 \mathrm{f}_j 放在 \mathrm{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;
}
然后，我们发现在表达式中不等号两侧都有 a_i\times a_j 所以，我们可以简化，即：
bool cmp(node x,node y){
return y.a*x.b+y.b>x.a*y.b+x.b;
}
整体伪代码
我们将上面两种方面拼在一起，即可得到完整的伪代码：
/*头文件*/
/*定义*/
/*比较函数*/
signed main(){
/*输入*/
/*排序*/
/*初始化*/
for(/*遍历 i*/){
for(/*遍历 j*/){
//状态转移
}
//更新答案
}
/*输出*/
}