Solution
题意简述
现在有 $N$ 个线性函数 $f_1,\dots,f_N$。函数 $f_i(x)=A_ix+B_i$。
找到一个长度为 $K$ 的序列 $p=(p_1,\dots,p_k)$，序列元素为 $K$ 个大小在 $[1,N]$ 的不同整数。
输出 $f_{p_1}(f_{p_2}(\dots f_{p_k}(1)\dots))$ 可能的最大值。
思路
贪心+DP。
假设现在已经选出了序列 $p$，考虑怎么放（放外层还是内层）答案更优。
钦定 $i<j$，则有两种放法：$f_i(f_j(x))$ 和 $f_j(f_i(x))$。
把 $A$，$B$ 代入：$A_iA_jx+A_iB_j+B_i$ 和 $A_iA_jx+A_jB_i+B_j$。发现其实只有后两项不同，我们钦定排序后越前面的放在越里层，所以我们可以定下排序规则为：
$$ A_iB_j+B_i现在取序列 $p$ 是直接取后 $k$ 个就可以了吗？
不对。因为以上排序规则只是解决了怎么放的问题，都是在已经选好了 $p$ 的前提假设下。那怎么取呢？考虑 DP 即可。
经典二维 DP：$f_{i,j}$ 表示当前第 $i$ 个，已选 $j$ 个的最大可能答案。转移就是选与不选，由于我们的排序规则是想越前面的放里层，所以直接从前往后转移就好了，不用倒着转移。