很好一道贪心

思路

首先发现$1\leq K\leq10$，考虑设计一个状态$f_{i,j}$表示在前$i$个中选中$j$个函数的最大值，初始化$f_{i,0}$为$1$，但是写转移方程的时候就会发现：当前访问的函数你无法确定当前的函数到底在哪一个位置上。

那怎么办？

注意到对于一下两个式子$f_1(f_2(x))$和$f_2(f_1(x)$，它们分别等于$a_1a_2x+a_1b_2+b_1$和$a_1a_2x+a_2b_1+b_2$。巧了，它们都共同有一个项：$a_1a_2x$，这就意味着他们两个的值的大小关系与$x$没有任何关系，这就可以让我们排序了。

接着再看回前面的DP，排序后访问到每一个函数你都可以确定它应该放在最外面，不然它的最终结果就会更小，这样我们就可以以$O(nlog_n+nk)$解决了。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
struct node{int a,b;}a[N];
bool cmp(node n1,node n2){return (n1.a-1)*n2.b<(n2.a-1)*n1.b;}
int f[N][15],n,k;
signed 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+n+1,cmp);
	for(int i=0;i<=n;i++)f[i][0]=1;
	for(int i=1;i<=n;i++)for(int j=1;j<=k;j++)
	{
		f[i][j]=max(f[i-1][j],a[i].a*f[i-1][j-1]+a[i].b);
	}
	printf("%lld\n",f[n][k]);
	return 0;
}