当前位置：首页 > news >正文

？？？ABC366:F - Maximum Composition（dp，无序：贪心排序）

news 2025/6/29 5:24:23

问题陈述

给你 NN 个线性函数 f1,f2,…,fNf1,f2,…,fN ，其中 fi(x)=Aix+Bifi(x)=Aix+Bi .

求由 KK 组成的序列 p=(p1,p2,…,pK)p=(p1,p2,…,pK) 中 fp1(fp2(…fpK(1)…))fp1(fp2(…fpK(1)…)) 的最大可能值。介于 11 和 NN (含)之间的个不同整数的最大可能值 fp1(fp2(…fpK(1)…))fp1(fp2(…fpK(1)…)) 。

限制因素

1≤N≤2×1051≤N≤2×105
1≤K≤min(N,10)1≤K≤min(N,10)
1≤Ai,Bi≤501≤Ai,Bi≤50 (1≤i≤N)(1≤i≤N)
所有输入值均为整数。

做法

我们看到这题肯定是想到了dp。但是吧，这题是要考虑顺序的，就是从n个中选k个，这k个数字的顺序会影响答案。那怎么办呢，我们肯定是不想要去考虑那个顺序的，我们就想把它先排好序。那就看看他能不能排序。我们假设i排在j前更好，那么就有Ai(Aj+Bj) + Bi > Aj(Ai+Bi) + Bj，即Ai*Bj + Bi > Aj*Bi + Bj。把i和i的放在一起,且i的必须放在左边，不然会出错，可能是我们已经加设了i排在j前更好吧，不太懂。然后得到Bi-AjBi > Bj-AiBj，即Bi（1-Aj） > Bj（1-Ai）。然后你可以选择用Bi（1-Aj）排序，或者Bj（1-Ai）排序。

排完序就好办了，dp数组下标：第i到n个选了j个；值：f函数的总值。我们为啥要倒着从n到1来遍历呢，因为函数是从外到里嵌套的，就是根据那个排序来的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
int dp[200010][20];//下标：第i到n个选了j个  值：f函数的总值 bool cmp(pair<int,int> a,pair<int,int> b){//贪心 //return b.second*(a.first-1) > b.first*(a.second-1);错误的return 1ll*a.second*(1-b.first)>1ll*b.second*(1-a.first);
}signed main(){scanf("%lld%lld",&n,&k);vector< pair<int,int> > v(n+1);for(int i=1;i<=n;i++){cin>>v[i].first>>v[i].second;}sort(v.begin()+1,v.end(),cmp);for(int i=1;i<=n+1;i++){for(int j=0;j<=10;j++){dp[i][j]=-1e6;}}dp[n+1][0]=1;//起初f(x)函数的x是1 for(int i=n;i>=1;i--){for(int j=0;j<=k;j++){dp[i][j]=max(dp[i][j],dp[i+1][j]);//不选 if(j) dp[i][j]=max(dp[i][j],1ll*v[i].first*dp[i+1][j-1]+v[i].second);}}cout<<dp[1][k];}