为了避免浮点运算,不妨将$f_{i}$乘上$C=10^{2}$,问题即求$\max_{S\subseteq [1,n]}\frac{\sum_{i\in S}(C^{2}-(\sum_{j\in S}f_{j}-f_{i})f_{i})s_{i}}{C^{2}}$
记$F=\sum_{i\in S}f_{i}$,考虑枚举$F$,并以$f_{i}$为质量、$(C^{2}-(F-f_{i})f_{i})s_{i}$为价值,问题即是要求质量和恰为$F$的最大价值和,可以通过01背包解决
考虑此时的复杂度,$F$的范围为$Cn$,复杂度即$o(C^{2}n^{3})$,无法通过
事实上,最优解满足$F\le C\sqrt{n}$,证明如下:
注意到随着$F$的增大价值降低,因此不妨将"质量和恰为$F$"改为不超过$F$
如果某人价值为负,那么不选一定更优,因此即$\forall i\in S,(C^{2}-(F-f_{i})f_{i})s_{i}\ge 0$
去掉$s_{i}$再将其对所有$i$求和,整理后即$F^{2}-|S|C^{2}\le \sum_{i\in S}f_{i}^{2}$
去掉$s_{i}$并乘上$f_{i}$,再将其对所有$i$求和,整理后即$\sum_{i\in S}f_{i}^{2}\le \frac{\sum_{i\in S}f_{i}^{3}
}{F}+|S|C^{2}$
将两式联立,即$F^{2}-|S|C^{2}\le \frac{\sum_{i\in S}f_{i}^{3}
}{F}+|S|C^{2}$
显然$|S|\le n$且$\frac{\sum_{i\in S}f_{i}^{3}}{F}\le F^{2}$,由此放缩即$F^{2}\le nC^{2}$,也即$F\le C\sqrt{n}$
由此,复杂度降为$o(C^{2}n^{2})$,可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 105 4 #define C 100 5 #define ll long long 6 int t,n,m,a[N]; 7 ll ans,s[N],f[N*C]; 8 double p; 9 int main(){ 10 scanf("%d",&t); 11 while (t--){ 12 scanf("%d",&n); 13 m=ans=0; 14 for(int i=1;i<=n;i++){ 15 scanf("%lld%lf",&s[i],&p); 16 a[i]=floor(p*C+0.5); 17 m+=a[i]; 18 } 19 m=C*((int)sqrt(n)+1); 20 for(int F=0;F<=m;F++){ 21 for(int i=0;i<=F;i++)f[i]=0; 22 for(int i=1;i<=n;i++){ 23 ll S=(C*C-(F-a[i])*a[i])*s[i]; 24 for(int j=F;j>=a[i];j--)f[j]=max(f[j],f[j-a[i]]+S); 25 } 26 ans=max(ans,f[F]); 27 } 28 printf("%lld.",ans/(C*C)); 29 ans%=C*C; 30 if (ans<1000)printf("0"); 31 if (ans<100)printf("0"); 32 if (ans<10)printf("0"); 33 printf("%lld00000\n",ans); 34 } 35 return 0; 36 }View Code