[hdu7033]Typing Contest

为了避免浮点运算,不妨将$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})$,可以通过

[hdu7033]Typing Contest
 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

 

上一篇:AtCoder Beginner Contest 172 (C题前缀和 + 二分,D题筛因子,E题容斥定理)


下一篇:【USACO 2021 January Contest, Platinum】Problem 1. Sum of Distances