链接
Problem - L - Codeforces
题目大意
有数为M 如何分解为a+b+c+...=M 并且这些数的最小公倍数最大
题目思路
由质因数分解可知最后的最大ans =
那么M=a+b+c就可看为
那么问题就转为在满足M的情况下让ans最大
易知x次数一般只有个位数 而3e4以内质因数只有3e3
那么对于背包 来说时间复杂度 为 质因数个数3e3*背包容量3e4*x次数约等于5e8
状态转移方程
第一维是滚动数组 第二维是当前剩余容量 值代表ans 注意预处理ln和prime
dp[now][k-jj]=max(dp[now][k-jj],dp[last][k]+ln[jj]);
题目代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e4+10;
int Mark[maxn];
int prime[maxn];
double ln[maxn];
double dp[3][maxn];//判断是否是一个素数 Mark 标记数组 index 素数个数
int Prime(){ int index = 0; memset(Mark,0,sizeof(Mark)); //cout<<1; for(int i = 2; i <= 3e4; i++) { //如果未标记则得到一个素数 if(Mark[i] == 0){ prime[++index] = i; } //标记目前得到的素数的i倍为非素数 for(int j = 1; j <= index && prime[j] * i <= 3e4; j++) { Mark[i * prime[j]] = 1; if(i % prime[j] == 0){ break; } } } return index;
}
int pnum;
void init()
{//memset(dp,1,sizeof dp);for(int i=0;i<=3e4;i++){dp[0][i]=0;} pnum=Prime();for(int i=1;i<=3e4;i++){ln[i]=log(i);}
}
int T;
int ans[maxn];
void solve()
{for(int i=1;i<=pnum;i++){int now=i%2;int last=(i+1)%2;for(int j=0;pow(prime[i],j)<=3e4;j++) {int jj=pow(prime[i],j);if(jj==1)jj=0;for(int k=3e4;k>=jj;k--){//dp[now][k-jj]=max(dp[now][k-jj],dp[last][k-jj]);dp[now][k-jj]=max(dp[now][k-jj],dp[last][k]+ln[jj]);} }}
}
int main()
{init();solve();//cout<<pnum<<endl; cin>>T;while(T--){int now;scanf("%d",&now);int nn=3e4-now;printf("%.8lf\n",dp[pnum%2][nn]);//printf("%.7lf\n",max(dp[pnum%2][nn],dp[(pnum+1)%2][nn]));}return 0;
}