ABC366F Maximum Composition 题解
题目大意
给定 \(N\) 个一次函数 \(f_i(x)=a_ix+b_i\)，从中选出 \(K\) 个函数 \(f_{p_1},f_{p_2},\dots,f_{p_K}\)，使得 \(f_{p_1}(f_{p_2}(\dots f_{p_K}))\) 最大，求最大值。
Solve
考虑这样一种情况：我已经选定 \(p_{k+1},p_{k+1},\dots,p_K\)，现在要去选 \(p_k\) 和 \(p_{k-1}\)，那么对于候选的 \(i,j\)，怎么选更优？
令 \(T=f_{p_{k+1}}(f_{p_{k+2}}(\dots f_{p_K})\)。那么选 \(p_k=i\) 更优当且仅当
\[\begin{align} a_j(a_iT+b_i)+b_j&>a_i(a_jT+b_j)+b_i\\ \iff a_jb_i+b_j&>a_ib_j+b_i\\ \iff (a_j-1)b_i&>(a_i-1)b_j \end{align} \]故我们贪心地按 \((a_j-1)b_i>(a_i-1)b_j\) 的规则将 \(f\) 排序，即可确定嵌套的先后顺序，排在前面的嵌套时更靠里。
既然我们已经知道了先后顺序，求最值可以 dp 求解。
设 \(g_{i,j}\) 表示仅从前 \(j\) 个函数里选， \(f_{p_i}(f_{p_{i+1}}(\dots f_{p_K}))\) 的最大值。则有 \(g_{i,j}=\max(g_{i,j-1},a_j\cdot g_{i-1,j-1}+b_j)\)。
Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
short f=1;
int x=0;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int N=2e5+10,K=15;
int n,m,tot;
long long f[K];
struct zzn{int a,b;}a[N];
bool cmpp(zzn x,zzn y){return x.b*(y.a-1)>y.b*(x.a-1);}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i=-~i) a[i]={read(),read()};
sort(a+1,a+n+1,cmpp);
f[0]=1;
for(int i=1;i<=n;i=-~i)
for(int j=m;j;j--)
f[j]=max(f[j],f[j-1]*a[i].a+a[i].b);
return printf("%lld",f[m]),0;
}