凸函数相关问题

Published: November 10, 2020 by Daltao

Categories:
algorithm 101

基础知识
最大和问题

基础知识

一个函数 $f$ 是上凸函数，当且仅当对于任意 $a\lt c$ ，记录 $b=(a+c)/2$ ，有 $2f(b)\geq f(a)+f(c)$ 。
一个函数 $f$ 是下凸函数，当且仅当对于任意 $a\lt c$ ，记录 $b=(a+c)/2$ ，有 $2f(b)\leq f(a)+f(c)$ 。
如果函数 $f$ 在定义域上二次可微，且 $f''\geq 0$ ，则 $f$ 是下凸函数，若 $f''\leq 0$ ，则 $f$ 是上凸函数。
函数 $a^x$ 是下凸函数，如果 $a\geq 0$ 。
函数 $\ln x$ 是上凸函数， $\exp(x)$ 是下凸函数。
函数 $x^n$ 在 $[0,+\infty)$ 上，若 $0\leq n\leq 1$ ,则为上凸函数，若 $x\geq 1$ ，则为下凸函数。

命题1：如果函数 $f$ 和函数 $g$ 都是上凸（下凸）函数，则它们的和 $f+g$ 也是上凸（下凸）函数。

证明：略。

命题2：如果函数 $f$ 和函数 $g$ 都是上凸函数，则它们的和 $\min(f,g)$ 也是上凸函数。

证明：略。

命题3：如果函数 $f$ 和函数 $g$ 都是下凸函数，则它们的和 $\max(f,g)$ 也是下凸函数。

证明：略。

命题4：如果函数 $f$ ， $g$ 是上凸（下凸）函数，且 $f$ 递增，则 $f(g)$ 也是上凸（下凸）函数。

证明：略。

最大和问题

题目1：给定 $m$ 个线性函数 $f_1,\ldots,f_m$ ，其中 $f_i(x)=a_ix+b_i$ ，现在我们希望为 $m$ 个非负整数未知变量 $x_1,\ldots,x_m$ 赋值，且要求满足 $\max_{i=1}^mx_i=n$ ，在满足约束条件下，要求 $\sum_{i=1}^nf_i(x_i)$ 尽可能大。

我们可以这样来理解这个问题，首先我们有 $m$ 个可投资对象和 $n$ 个资源，且已经获利 $\sum_{i=1}^mb_i$ ，接下来如果我们为第 $i$ 个可投资对象每投入一单位资源，那么就能获利 $a_i$ ，问最大获利多少。

这个自然是将所有资源都砸在 $a_i$ 最大的可投资对象上了。

题目2：给定 $m$ 个函数 $f_1,\ldots,f_m$ ，且每个函数的成像都构成一个上凸包，现在我们要求为 $m$ 个非负整数未知变量 $x_1,\ldots,x_m$ 赋值，且要求满足 $\sum_{i=1}^mx_i=n$ ，在满足约束条件下，要求 $\sum_{i=1}^nf_i(x_i)$ 尽可能大。其中 $1\leq m,n\leq 10^5$

利用题目1的方式，我们来试图重新解读问题。首先我们有 $m$ 个可投资对象和 $n$ 个资源，且已经获利 $\sum_{i=1}^mf_i(0)$ ，接下来如果我们为第 $i$ 个可投资对象每投入一单位资源，那么就能获利 $f_i(x+1)-f_i(x)$ （ $x$ 是已经向第 $i$ 个可投资对象投入的资源总量），问最大获利多少。

我们会发现由于所有的函数都是上凸包，因此对于任意 $i$ ， $d_i(x+1)=f_i(x+1)-f_i(x)$ 是非严格递减函数。考虑到 $d_i(1)\geq d_i(2)\geq \ldots$ ，因此在最终结果中，如果选择 $d_i(x+1)$ 那么我们必定也会选择 $d_i(x)$ ，因此我们可以将所有可选的收益一开始就全部展开 ${d_i(x)}$ ，现在我们要做的就是从 $d_i(x)$ 中选择正好 $n$ 个元素，且元素之和最大。这个步骤自然我们会选择使用贪心算法来完成。

现在回到问题，如果我们把所有方案都展开，那么可能会有 $nm$ 个选择，这样太多了，但是由于我们在取得 $d_i(x)$ 之前是不会考虑 $d_i(x+1)$ 的，因此我们可以对每个 $i$ ，仅考虑 $x$ 最小且未被选择的 $d_i(x)$ 。实际操作中，我们只需要维护一个大小为 $m$ 的大根堆即可，当我们将 $d_i(x)$ 弹出的同时，将 $d_i(x+1)$ 加回即可，总的时间复杂度为 $O(n\log_2m)$ 。

提供一道SGU的问题。

题目3：给定 $m$ 个函数 $f_1,\ldots,f_m$ ，且每个函数的成像都构成一个上凸包，现在我们要求为 $m$ 个非负整数未知变量 $x_1,\ldots,x_m$ 赋值，且要求满足 $\sum_{i=1}^mx_i=n$ ，在满足约束条件下，要求 $\sum_{i=1}^nf_i(x_i)$ 尽可能大。其中 $1\leq m\leq 10^5$ , $1\leq n\leq 10^{18}$

这个问题是今天比赛的一道题目学到的。由于是上凸包，因此我们可以用三分算法为每个函数找到其极值点（在非负整数定义域下），记 $f_i$ 的极值点在 $p_i$ 处取到。

分两种情况讨论，如果 $n\leq \sum_{i=1}^m p_i$ ，那么我们可以断定一定有 $x_i\leq p_i$ ，否则对应的就有 $x_i\geq p_i$ 。

如果是 $n\leq \sum_{i=1}^m p_i$ 的情况。记 $d_i(x)=f_i(x)-f_i(x-1)$ 称为函数 $f_i$ 在点 $x$ 处的增量。很显然最优解中，采用的最小增量一定是最大的，我们可以通过二分法找到这个最小增量，这里的时间复杂度为 $O(n(\log_2M)^2)$ ，其中 $M$ 是数据范围。找到最小增量 $\delta$ 后，我们将 $x_i$ 设置为 $f_i$ 增量大于等于 $\delta$ 的整数点数目（不包括0）。那么此时可能会有 $\sum_{i=1}^mx_i>n$ 的情况出现，我们可以保证所有函数增量大于 $\delta$ 的整数点都会被保留（否则为什么要使用增量为 $\delta$ 的点呢？），而增量为 $\delta$ 的点可以删除一部分，来满足 $\sum_{i=1}^mx_i>n$ ，这一部分的时间复杂度为 $O(m)$ 。

对于 $n\geq \sum_{i=1}^m p_i$ 的情况，与上面的方法类似。

最后总的时间复杂度为 $O(m(\log_2M)^2)$ 。

提供一道题目。

题目4：给定 $n$ 个非严格递增数组 $a_1,a_2,\ldots,a_n$ ，长度分别为 $t_1,\ldots,t_n$ 。之后要求执行正好 $m$ 次操作，每次操作选择一个非空的数组头，并且删除数组头部元素。要求 $m$ 次操作后删除的元素总和最大。输入满足 $1\leq n,m\leq 3000$ ，且 $m\leq \sum_{i=1}^nt_i\leq 10^6$ ，每个数组元素在 $0$ 到 $10^9$ 之间。

一般的DP做法时间复杂度为 $O(nm\sum_{i=1}^nt_i)$ ，太慢了。

很显然我们最多只会有一个数组的元素是部分取走的。因此就得出了我们的思路，一种预处理前后缀的做法的时间复杂度为 $O(nm^2+\sum_{i=1}^nt_i)$ ，还是不够好。

这里我们可以神奇的套上分治。类似与并行二分，我们可以将要处理的数组分为两部分，之后在左边的数组上暴力计算DP，并在递归处理右部分的时候作为初始值下传。可以发现抵达叶子（区间只有一个元素）的时候，这时候其余元素都被处理到了。

树的每一层的时间复杂度都是 $O(nm)$ ，最后一层的时间复杂度为 $O(\sum_{i=1}^n t_i)$ 。因此总的时间复杂度为 $O(nm\log_2n + \sum_{i=1}^nt_i)$ 。

提供一道题目。

并且由于背包问题中交换商品顺序不影响结果，因此可以用可撤销队列来做，时间复杂度也是 $O(nm\log_2n + \sum_{i=1}^nt_i)$ 。

题目5：给定 $m$ 个函数 $f_1,\ldots,f_m$ ，且每个函数的成像都构成一个上凸包，且每个函数的值域都是正数，现在我们要求为 $m$ 个非负整数未知变量 $x_1,\ldots,x_m$ 赋值，且要求满足 $\sum_{i=1}^mx_i=n$ ，在满足约束条件下，要求 $\prod_{i=1}^nf_i(x_i)$ 尽可能大。其中 $1\leq m\leq 10^5$ , $1\leq n\leq 10^{18}$ 。输出最大可能的乘积，结果对 $P$ 取模。

我们希望 $\prod_{i=1}^nf_i(x_i)$ 最大，等价于希望 $\sum_{i=1}^n\ln f_i(x_i)$ 最大。考虑到 $\ln f_i$ 也是个上凸包，因此我们可以用问题3的方式找到每个函数的赋值方案，之后算出真实的乘积即可。时间复杂度为 $O(n\log_2m\log_2M)$ 。