为了避免浮点运算，不妨将$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 }