凸函数相关问题

Published: by Creative Commons Licence

  • Tags:

基础知识

  • 一个函数$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)$。