ABC366F

dengrongkuo / 2024-08-11 / 原文

题目

F - Maximum Composition
给定 $n$ 个函数 $f_i$，其中 $f_i(x) = a_i x + b_i$。
对于所有元素互不相同的序列 $p = (p_1, p_2, \cdots, p_k)$，其中所有元素均在 $[1, n]$ 中，求 $f_{p_1}(f_{p_2}(\cdots(f_{p_k}(1))))$ 的最大值。
$1 \leq n \leq 2 \times 10^5$，$1 \leq k \leq \min\{ n, 10 \}$，$1 \leq a_i, b_i \leq 50$。

题解

首先有一个很显然的性质，就是这个复合函数是单调递增的。因此若 $p$ 的前面确定，则只需最大化后面的函数值。
考虑对于给定的一组 $p_k$，将它们如何排列才能使得答案最大。
假设我们已经找到了一组最优解 $p$。
考虑对于 $p$ 中相邻的两项 $i$ 和 $j$，其中 $i$ 在 $j$ 前面，交换它们的顺序对函数值的大小有什么影响。由上面的分析，对整体函数值的影响等价于对以 $i$ 开头的后缀的函数值的影响。而又由假设，$j$ 之后的函数值是确定的，因此只需比较以下两个函数的大小：

\[f_i(f_j(x)), f_j(f_i(x)) \]

把它们的表达式写出来，得

\[f_i(f_j(x)) = a_i(a_j x + b_j) + b_i = a_i a_j x + a_i b_j + b_i \]

\[f_j(f_i(x)) = a_j(a_i x + b_i) + b_j = a_i a_j x + a_j b_i + b_j \]

由最优解的假设，必有 $f_i(f_j(x)) \geq f_j(f_i(x))$。这等价于

\[a_i b_j + b_i \geq a_j b_i + b_j \]

移项，得

\[(a_i - 1)b_j \geq (a_j - 1)b_i \]

移项，得

\[\dfrac{a_i - 1}{b_i} \geq \dfrac{a_j - 1}{b_j} \]

因此，对变量 $i$，最优解 $p$ 一定满足 $\dfrac{a_i - 1}{b_i}$ 的值单调不增。

因此，只需将给定的数组 $\{(a_i, b_i)\}$ 按 $\dfrac{a_i - 1}{b_i}$ 从大到小排序，然后 01 背包即可。
时间复杂度为 $\Theta(nk)$。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=200003,M=13;
const long long NIN=-1e17;
int n,m,a[N],b[N],c[N];
long long f[N][M];
bool cmp(const int& u,const int& v){
	return (a[u]-1)*b[v]<(a[v]-1)*b[u];
}
int main(){
//	freopen("composition.in","r",stdin);
//	freopen("composition.out","w",stdout);
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]);
	for(i=1;i<=n;i++) c[i]=i;
	sort(c+1,c+n+1,cmp);
	memset(f,NIN,sizeof f);
	f[0][0]=1;
	for(i=1;i<=n;i++)
		for(j=1,f[i][0]=1;j<=m;j++)
			f[i][j]=max(f[i-1][j],f[i-1][j-1]*a[c[i]]+b[c[i]]);
	printf("%lld",f[n][m]);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}