此题的亮点在于利用map来维护一个当前所有数可以凑成的最大公约数
的集合,相当于缩小了值域,进而可以采用01背包的做法来dp出最优解
算法1
(gcd+01背包)
//一维map dp写法
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n;
int a[310],b[310];
map<int,int> dp;//dp[i]表示最大公约数为i时的最小代价
//可以开一维,是因为在每一次用dp[x]更新dp[d]时,因为x>=d恒成立
//所以永远都是大数更新小数。又因为map是从小到大遍历的,因此小数在被更新后不会被重复遍历,相当于实现了一维01背包的过程
int gcd(int a,int b)
{
if(!b) return a;
return gcd(b,a%b);
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
dp[0]=0;//提前往集合内放入0,0和任意数x取gcd都是x本身
for(int i=1;i<=n;i++)
{
//使用集合来优化遍历1~1e9的过程,相当于缩小了值域
for(auto [x,y] :dp)
{
int d=gcd(x,a[i]);
if(dp.count(d))//dp集合内已经存在这个最大公约数时,可以将这个最大公约数的新方案和原来的方案比较,取最小值
{
dp[d]=min(dp[d],y+b[i]);
}
else//若原来就不存在该最大公约数,则这个答案就可以成为当前的最小值(相当于原来的dp数组初始化成了inf)
{
dp[d]=y+b[i];
}
}
}
int ans=(dp.count(1))?dp[1]:-1;
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t=1; //cin>>t;
while(t--) solve();
return 0;
}
2
(gcd+01背包)
//二维dp写法
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n;
int a[310],b[310];
map<int,int> dp[310];//dp[i][j]表示考虑前i个数,选择若干个数,使最大公约数为j的最小代价
int gcd(int a,int b)
{
if(!b) return a;
return gcd(b,a%b);
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
//对于前i个数,第i个数可以不选,因此前i-1个数可形成的所有最大公约数也要提前转移一遍
for(auto [x,y] :dp[i-1]) dp[i][x]=y;
//再更新 新的最大公约数的最小代价
for(auto [x,y] :dp[i-1])
{
int d=gcd(x,a[i]);
if(dp[i].count(d)) dp[i][d]=min(dp[i][d],y+b[i]);
else dp[i][d]=y+b[i];
}
}
int ans=(dp[n].count(1))?dp[n][1]:-1;
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t=1; //cin>>t;
while(t--) solve();
return 0;
}