• 周五. 7月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu7033]Typing Contest

admin

11月 28, 2021

为了避免浮点运算,不妨将$f_{i}$​​​乘上$C=10^{2}$​​​,问题即求$max_{Ssubseteq [1,n]}frac{sum_{iin S}(C^{2}-(sum_{jin S}f_{j}-f_{i})f_{i})s_{i}}{C^{2}}$​​​

记$F=sum_{iin S}f_{i}$​​,考虑枚举$F$​​,并以$f_{i}$​​为质量、$(C^{2}-(F-f_{i})f_{i})s_{i}$​​为价值,问题即是要求质量和恰为$F$​​的最大价值和,可以通过01背包解决

考虑此时的复杂度,$F$的范围为$Cn$,复杂度即$o(C^{2}n^{3})$,无法通过

事实上,最优解满足$Fle Csqrt{n}$​​​​​​,证明如下:

注意到随着$F$的增大价值降低,因此不妨将”质量和恰为$F$”改为不超过$F$​

如果某人价值为负,那么不选一定更优,因此即$forall iin S,(C^{2}-(F-f_{i})f_{i})s_{i}ge 0$​

去掉$s_{i}$​再将其对所有$i$​求和,整理后即$F^{2}-|S|C^{2}le sum_{iin S}f_{i}^{2}$​

去掉$s_{i}$​​​并乘上$f_{i}$​​​,再将其对所有$i$​​​求和,整理后即$sum_{iin S}f_{i}^{2}le frac{sum_{iin S}f_{i}^{3}
}{F}+|S|C^{2}$​​​​​

将两式联立,即$F^{2}-|S|C^{2}le frac{sum_{iin S}f_{i}^{3}
}{F}+|S|C^{2}$​

显然$|S|le n$​​​且$frac{sum_{iin S}f_{i}^{3}}{F}le F^{2}$​​​​​,由此放缩即$F^{2}le nC^{2}$​​​,也即$Fle Csqrt{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
",ans);
34     }
35     return 0;
36 } 

View Code

发表评论

您的电子邮箱地址不会被公开。