本文迁移自洛谷原文。
考虑到最多只会有一个 。
那么我们可以考虑类似 meet-in-the-middle 的做法。
令 表示考虑了前 个数，此时乘积为 ， 的最大值， 的定义类似，不过是从 开始倒着的。dp 的时候枚举 ，枚举 ，再枚举满足 第二维大小的所有 即可。
则我们这种情况下的最好答案就是枚举一个中间断点 ，和 左边的部分的乘积 ， 的最小值了。
此时我们需要证明，在所有选择的 都 的情况下， 和 的第二维都只要开到 即可。
不妨设一个 ，初始为 最大的位置，令 为 左边所有 的乘积， 为 右边所有 的乘积。
我们贪心的考虑，如果 ，就让 ；如果 ，就让 。在移动 的同时维护 和 的值。
此时第二维就需要开到一个 的大小。因为 是 级别的，所以 ，故第二维只需要开到 即可。因为 ，所以 ，得证。
综上，该部分复杂度为 。
那么我们可以直接枚举这个 ，发现 左侧和右侧 的乘积均 。令 表示现暂时不选 ，其他所有位置都选之后乘积为 时的最大值。这个可以利用 和 快速处理。
然后我们枚举除了 的所有 的乘积 ，推出 的值最小是多少，计算出 即第 个数的贡献，乘上 即可。
该部分复杂度为 。
综上，总复杂度为 ，可以不知道为什么但只跑了 1.5s 通过此题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
const int B=177830;
const int B2=6600;
int n,w,a[103];
double f[103][B+3],g[103][B+3],ans;
vector<int>v;
double h[B2+3];
int main(){
cin>>n>>w;
for(int i=1;i<=n;i++)
cin>>a[i];
f[0][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=B;j++)
for(int k=1;k<=B/j;k++)
f[i][j*k]=max(f[i][j*k],f[i-1][j]*(1.0*(a[i]/k)/a[i]));
for(int j=B;j>0;j--)
f[i][j]=max(f[i][j],f[i][j+1]);
}
g[n+1][1]=1;
for(int i=n;i;i--){
for(int j=1;j<=B;j++)
for(int k=1;j*k<=B;k++)
g[i][j*k]=max(g[i][j*k],g[i+1][j]*(1.0*(a[i]/k))/a[i]);
for(int j=B;j>0;j--)
g[i][j]=max(g[i][j],g[i][j+1]);
}
for(int i=0;i<=n;++i)for(int j=1;j<=B;++j)
if((w+j-1)/j<=B)ans=max(ans,f[i][j]*g[i+1][(w+j-1)/j]);
for(int i=1;i<=n;++i){
if(1){
for(int j=1;j<=B2;++j)h[j]=0;
for(int j=1;j<=B2;++j)
for(int k=1;k*j<=B2;++k)
h[j*k]=max(h[j*k],f[i-1][j]*g[i+1][k]);
for(int j=B2;j;--j)h[j]=max(h[j],h[j+1]);
for(int j=1;j<=B2;++j){
int ee=(w+j-1)/j;ee=max(ee,1);
if(ee>a[i])continue;
int e2=a[i]/ee;
ans=max(ans,1.0*e2/(1.0*a[i])*h[j]);
}
}
}
cout<<fixed<<setprecision(15)<<ans*w<<'\n';
}
|