L - Clock Master Gym - 102798L

L - Clock Master Gym - 102798L

题意：

给定一个数字n，令n=a1+a2+a3…求lcm(a1,a2,a3,…)的最大值,以loge(x)的形式输出

题解：

lcm要求尽可能大，我们就要保证a1,a2,a3…尽可能为质数或质数的整数次幂，我们假设a1是p1^x,a2是p2^y,p1和p2是不同的质数，x的取值范围是[1~m],p1^m<=n,x有且只能在这个取值范围中取一个，也就是我们按照质数的种类分组，每组中是不同的幂次。
我们将每个素数的不同幂次划分为一组，每个组我们最多只能选一个(也可以不选)，问在n范围内，所能选的p1 * p2 *…的最大值
这个看着像什么？

有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是v[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

没错就是分组背包，容量V就是n，每组的物品就是p1的整数次幂，价值就是所选p1的整数次幂去log(因为题目输出要求)，费用就是p1的整数次幂

log(p1 * p2 * p3…) = log(p1)+log(p2)+…
所以直接累加lg[x]
预处理出所有答案

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e4 + 10;
const int mod = 1e9 + 7;
int pri[N], tot;
double dp[N], Log[N];
bool vis[N];
void init() {
    memset(vis, 0, sizeof(vis));
    vis[0] = vis[1] = 1;
    tot = 0;
    for(int i = 2; i < N; ++i) {
        if(!vis[i]) {
            pri[++tot] = i;
            for(int j = i + i; j < N; j += i)
                vis[j] = 1;
        }
    }
    for(int i = 0; i < N; ++i) Log[i] = log(i);//首先预处理出log答案 
    for(int i = 1; i <= tot; ++i) {//对于tot个分组 
        for(int j = N - 1; j >= pri[i]; --j) {//容量 
            for(int k = pri[i]; k <= j; k *= pri[i])//枚举pri[i]的整数次幂 
                dp[j] = max(dp[j], dp[j - k] + Log[k]);
        }
    }
}
 
 
int main() {
    init();
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        printf("%.9fn", dp[n]);
    }
    return 0;
}

最后

以上就是合适鸡为你收集整理的L - Clock Master Gym - 102798L的全部内容，希望文章能够帮你解决L - Clock Master Gym - 102798L所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。