ABC366F 题解

WerChange · 2024-08-12 11:14:20 · 题解

推荐在 cnblogs 上阅读

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。发现其实只有后两项不同，我们钦定排序后越前面的放在越里层，所以我们可以定下排序规则为：

移项一下：

现在取序列 p 是直接取后 k 个就可以了吗？

不对。因为以上排序规则只是解决了怎么放的问题，都是在已经选好了 p 的前提假设下。那怎么取呢？考虑 DP 即可。

经典二维 DP：f_{i,j} 表示当前第 i 个，已选 j 个的最大可能答案。转移就是选与不选，由于我们的排序规则是想越前面的放里层，所以直接从前往后转移就好了，不用倒着转移。

code