[hdu7033]Typing Contest

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

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define C 100
#define ll long long
int t,n,m,a[N];
ll ans,s[N],f[N*C];
double p;
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        m=ans=0;
        for(int i=1;i<=n;i++){
            scanf("%lld%lf",&s[i],&p);
            a[i]=floor(p*C+0.5);
            m+=a[i];
        }
        m=C*((int)sqrt(n)+1);
        for(int F=0;F<=m;F++){
            for(int i=0;i<=F;i++)f[i]=0;
            for(int i=1;i<=n;i++){
                ll S=(C*C-(F-a[i])*a[i])*s[i];
                for(int j=F;j>=a[i];j--)f[j]=max(f[j],f[j-a[i]]+S);
            }
            ans=max(ans,f[F]);
        }
        printf("%lld.",ans/(C*C));
        ans%=C*C;
        if (ans<1000)printf("0");
        if (ans<100)printf("0");
        if (ans<10)printf("0");
        printf("%lld00000
",ans);
    }
    return 0;
}