ABC366F Maximum Composition

传送门

Solution

设 $f_1(x)=a_1x+b_1$，$f_2(x)=a_2x+b_2$。若 $f_1(f_2(x))<f_2(f_1(x))$，则 $a_1b_2+a_1<a_2b_1+b_2$。又因为 $b_1,b_2>0$，移项得$\dfrac{a_1-1}{b_1}<\dfrac{a_2-1}{b_2}$。

因此对于选定的 $K$ 个 $f(x)$，从内到外 $\dfrac{a-1}{b}$ 应升序排列。

我们对 $N$ 个函数以 $\dfrac{a-1}{b}$ 为关键字升序排序，用 01 背包求解即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 2e5 + 10;

ll n, k, f[N];
struct Node {
    ll a, b;
    friend bool operator < (const Node &a, const Node &b) {
        return (a.a - 1) * b.b < (b.a - 1) * a.b;
    }
} a[N];

int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i].a, &a[i].b);
    sort(a + 1, a + 1 + n);
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = k; j; j--)
            f[j] = max(f[j], a[i].a * f[j - 1] + a[i].b);
    printf("%lld", f[k]);
    return 0;
}