CF1801F 题解

· · 题解

看到积式，我们自然能想到用 dp 来解决此类问题。

设 f_{i,j} 表示前 b_{1,2,\cdots,i} 的值已经确定，后面的数的限制为 \prod\limits_{p=i+1}^n b_p\geq j 的前提下， \prod\limits_{p=1}^i\lfloor\dfrac{a_p}{b_p}\rfloor \times \dfrac{1}{a_p} 的最大值。

自然可以通过枚举 b_i 的值来转移：

令 b_i=x ，则有转移： f_{i,\lceil\frac{j}{x}\rceil}\leftarrow f_{i-1,j}\times\lfloor\dfrac{a_p}{x}\rfloor \times \dfrac{1}{a_p}

初始状态为： f_{0,k}=1，答案为： f_{n,1}\times k。

直接转移是 O(nk) 的，考虑优化。

可以发现，第二维的值是由 k 不断除以整数后向上取整得到的。

向上取整有一个性质：

\lceil\dfrac{k}{a}\rceil=\lfloor\dfrac{k-1}{a}\rfloor+1

而且这个式子可以嵌套：

\lceil\dfrac{\lceil\frac{k}{a}\rceil}{b}\rceil=\lfloor\dfrac{\lfloor\frac{k-1}{a}\rfloor+1-1}{b}\rfloor+1=\lfloor\dfrac{\lfloor\frac{k-1}{a}\rfloor}{b}\rfloor+1=\lfloor\dfrac{k-1}{ab}\rfloor+1

这样我们就可以把向上取整转化为向下取整了，用类似杜教筛的转移方式就可以得到 O(nk^{0.75}) 的做法。

警钟长鸣：递归写法有可能被卡常，我考场上就被卡了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=105,N=7005;
int n,k,a[MAXN],v[N],m,id[10000001];
bool vis[MAXN][N];
double f[MAXN][N];
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; ++i)
        scanf("%d",&a[i]);
    if(k==1) {//记得特判k=1
        double ans=1.0;
        printf("%.20lf\n",ans);
        return 0;
    }
    for(int l=1,r; l<k; l=r+1) {
        r=(k-1)/((k-1)/l);
        v[++m]=(k-1)/l;
        id[v[m]]=m;
    }
    v[++m]=0,id[0]=m;//不要忘记还有1
    f[0][1]=1;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            if(f[i-1][j]) {
                for(int l=1,r; l<=v[j]; l=r+1) {
                    r=v[j]/(v[j]/l);
                    f[i][id[v[j]/r]]=max(f[i][id[v[j]/r]],(a[i]/l)/(double)a[i]*f[i-1][j]);
                }
                f[i][m]=max(f[i][m],(a[i]/(v[j]+1))/(double)a[i]*f[i-1][j]);
            }
    printf("%.15lf\n",f[n][m]*k);
    return 0;
}