bb

untergehen · 2025-11-17 21:15:01 · 题解

本题解复杂度是 \operatorname{O}(nk^{\frac23}\log k) 略优于其他题解。

首先显然最后 \prod{b_i}\le 2k，否则可以取出最大的那个 b_i，将他减一显然仍 \geq k。下文中将默认乘积 O(k)。

我们背包统计出前后缀 \prod {b_i}\le k^{\frac23} 时最大的 \prod{\lfloor \frac{a_i}{b_i}\rfloor}。同时将切割方法分为两类。

1. \exist i, b_i\geq k^{\frac13}

此时枚举 i，\operatorname{O}(k^{\frac23}\log k) 合并前后段 dp，整除分块枚举 b_i 即可。

2. otherwise

我们断言，直接枚举相邻的前后缀 dp 合并是对的。复杂度\operatorname{O}(k^{\frac23})。

若存在 \{b_i\} 使得不被计算。则考虑 b_i 前缀积第一个大于等于 k^{\frac23} 的位置。

因为要求，蓝色部分乘积小于等于 k^{\frac23} ,因为他同时不能被计算，所以红色部分应当大于等于 k^{\frac23} 这意味着中间的圆圈应当大于等于 k^{\frac13}。这意味着它应当属于第一类，被算过了。

综上该做法以 \operatorname{O}(nk^{\frac23}\log k) 时间 \operatorname{O}(nk^{\frac23}) 空间解决了该题。

#include<bits/stdc++.h>
#define N 105
#define hV 50005
using namespace std;
namespace shan{
    const double inf=1e18;
    int n,k,a[N];
    double pre[N][hV],suf[N][hV];
    double ls[hV];
    signed main(){
        cin>>n>>k;
        const int V=pow(k,0.666666)+1;
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=V+1;j++)
                pre[i][j]=suf[i][j]=-inf;
        pre[0][1]=suf[n+1][1]=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            for(int j=1;j<=min(V,a[i]);j++){
                double me=log(a[i]/j);
                for(int k=1;k*j<=5e4;k++)
                    pre[i][j*k]=max(pre[i][j*k],pre[i-1][k]+me);
            }
        }
        for(int i=n;i>=1;i--){
            for(int j=1;j<=min(V,a[i]);j++){
                double me=log(a[i]/j);
                for(int k=1;k*j<=V;k++)
                    suf[i][j*k]=max(suf[i][j*k],suf[i+1][k]+me);
            }
        }
        double ans=-inf;
        for(int j=k;j<=V;j++)ans=max(ans,suf[1][j]);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=V+1;j++)ls[j]=-inf;
            for(int j=1;j<=V;j++)
                for(int k=1;k*j<=V;k++)
                    ls[j*k]=max(ls[j*k],pre[i-1][j]+suf[i+1][k]);
            for(int j=V;j>=1;j--)
                ls[j]=max(ls[j],ls[j+1]);
            for(int l=1,r=0;l<=a[i];l=r+1){
                int val=a[i]/l;
                r=a[i]/val;
                int need=(k+r-1)/r;
                if(need<=V)
                    ans=max(ans,log(val)+ls[need]);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=V;j>=1;j--)
                suf[i+1][j]=max(suf[i+1][j],suf[i+1][j+1]);
            for(int j=1;j<=V;j++){
                int need=(k+j-1)/j;
                if(need<=V)
                    ans=max(ans,pre[i][j]+suf[i+1][need]);
            }
        }
        ans+=log(k);
        for(int i=1;i<=n;i++)ans-=log(a[i]);
        cout<<fixed<<setprecision(20)<<exp(ans);
        return 0;
    }
} 
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    shan::main();
    return 0;
}

有趣的知识：发现答案是乘积形式，可以取 \ln 乘改加，最后 \exp 回来。精度和速度都可能有所提升。