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