欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

L Clock Master(2020 China Collegiate Programming Contest Weihai Site)补题

程序员文章站 2022-06-07 11:43:40
...

L Clock Master(2020 China Collegiate Programming Contest Weihai Site)补题
题意:给你一个数b,求ans = b1 * b2 * b3 …最大,且b = b1+b2+b3…
其实就是求b1 ,b2, b3, b4 的最小公倍数的最大值。
思路:
任意一个数都可以质因数分解成
N = p1a1 * p2a2 * p3a3

所以我们可以这样来想这个问题
j将b看成是一个容量为b的背包;p1a1, p2a2,p3a3…不同的质数的不同次方看成是分成了一个组;这就是一个分组背包的问题了,从质数组中去选择,它们的和不超过b,求它们乘积的最大值。
注意:
①数据范围较大,需要将二维的dp优化为一维的dp
②数据较大,用log进行优化,打表进行处理
log(a*b) =log a + log b,所以状态转移方程为:
L Clock Master(2020 China Collegiate Programming Contest Weihai Site)补题
③用欧拉筛求出30010以内的素数。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 30010;
int primes[maxn];
bool vis[maxn];
int cnt;
double dp[maxn];
double logg[maxn];
//欧拉筛素数
void get_prime(){
	for(int i = 2;i <= maxn;i++){
		if(!vis[i]){
			primes[++cnt] = i;
		}
		for(int j = 1;primes[j] * i <= maxn;j++){
			vis[i*primes[j]] = true;
			if(i % primes[j]==0){
				break;
			}
		}
	}
	/*
	for(int i = 1;i<=cnt;i++){
	  cout<<primes[i]<<" ";
	}
	*/
} 
//打表,避免数据过大 
void init(){
	for(int i = 1;i <= maxn;i++){
		logg[i] = log(i);
	//	cout<<logg[i]<<" "; 
	}
	for(int i = 1;i <= cnt;i++){//选择的物品 (质数)
			for(int j = maxn;j >= primes[i];j--){//背包大小 
				for(int k = primes[i];k <= j ;k *= primes[i]){//物品幂次的选择 
					dp[j] = max(dp[j],dp[j-k] + logg[k]);
				     //不选择质数          选择质数(幂次) 
				}
			}
		}
}
int main(){
	get_prime();
	init();
	int t,b;
	cin>>t;
	while(t--){
		cin>>b;
		cout<<fixed<<setprecision(9)<<dp[b]<<endl;
	}
	return 0;
}

(有什么错误就指出来吧hhh…)

相关标签: 补题ccpc