网站建设公司客户开发手册,网站的seo优化方案,搜索引擎中注册网站,wordpress更换链接自动跳转问题陈述
给你 NN 个线性函数 f1,f2,…,fNf1,f2,…,fN #xff0c;其中 fi(x)AixBifi(x)AixBi .
求由 KK 组成的序列 p(p1,p2,…,pK)p(p1,p2,…,pK) 中 fp1(fp2(…fpK(1)…))fp1(fp2(…fpK(1)…)) 的最大可能值。介于 11 和 NN (含)之间的个不…问题陈述
给你 NN 个线性函数 f1,f2,…,fNf1,f2,…,fN 其中 fi(x)AixBifi(x)AixBi .
求由 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×1051≤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(AjBj) Bi Aj(AiBi) Bj即Ai*Bj Bi Aj*Bi Bj。把i和i的放在一起,且i的必须放在左边不然会出错可能是我们已经加设了i排在j前更好吧不太懂。然后得到Bi-AjBi Bj-AiBj即Bi1-Aj Bj1-Ai。然后你可以选择用Bi1-Aj排序或者Bj1-Ai排序。
排完序就好办了dp数组下标第i到n个选了j个 值f函数的总值。我们为啥要倒着从n到1来遍历呢因为函数是从外到里嵌套的就是根据那个排序来的。
#includebits/stdc.h
#define int long long
using namespace std;
int n,k;
int dp[200010][20];//下标第i到n个选了j个 值f函数的总值 bool cmp(pairint,int a,pairint,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 pairint,int v(n1);for(int i1;in;i){cinv[i].firstv[i].second;}sort(v.begin()1,v.end(),cmp);for(int i1;in1;i){for(int j0;j10;j){dp[i][j]-1e6;}}dp[n1][0]1;//起初f(x)函数的x是1 for(int in;i1;i--){for(int j0;jk;j){dp[i][j]max(dp[i][j],dp[i1][j]);//不选 if(j) dp[i][j]max(dp[i][j],1ll*v[i].first*dp[i1][j-1]v[i].second);}}coutdp[1][k];}
最后
还是不太理解吧那个排序函数写的我改成别的都过不去。
