数论+分组背包
打表找一找规律就发现了,我们不过是求这一个数组的最小公倍数,想办法让其最大
然后我们运用分组背包的想法,肯定里面的数互素的情况下才好。
#include<iostream> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int max_n = 31000; int a[max_n]; double dp[3500][max_n]; bool used[max_n]; int tot=0; double b[3500]; void init() { for (int i=2;i<max_n;++i) { if (used[i])continue; for (int j=i+i;j<max_n;j+=i) { used[j]=1; } a[++tot]=i; } for (int i=1;i<=tot;++i) { b[i]=log(a[i]); } } int main() { ios::sync_with_stdio(0); init(); int n = 30000; for (int i=1;i<=tot;++i) { for (int j=1;j<=n;++j) { dp[i][j]=dp[i-1][j]; int ex1=a[i]; double ex2=b[i]; while (j-ex1>=0) { dp[i][j]=max(dp[i][j],dp[i-1][j-ex1]+ex2); ex1*=a[i]; ex2+=b[i]; } } } int T;scanf("%d",&T); while (T--) { scanf("%d",&n); printf("%0.12llf\n",dp[tot][n]); } }