C++(g++ 7.5.0) 解法, 执行用时: 14ms, 内存消耗: 484K, 提交时间: 2022-11-21 17:11:12

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
const int N=310;
map<int,ll> dp,back;
PII a[N];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int len;
    cin>>len;
    for(int i=1;i<=len;i++){
        cin>>a[i].first;
    }
    for(int i=1;i<=len;i++){
        cin>>a[i].second;
    }
    for(int i=1;i<=len;i++){
        ll q=a[i].first,w=a[i].second;
        back=dp;
        if(!dp.count(q)) dp[q]=w;
        else dp[q]=min(dp[q],w);
        for(auto &[i,j]:back){
            int p=gcd(i,q);
            if(!dp.count(p)) dp[p]=j+w;
            else dp[p]=min(dp[p],j+w);
        }
    }
    if(dp.count(1)) cout<<dp[1];
    else cout<<-1;
}

C++(clang++ 11.0.1) 解法, 执行用时: 11ms, 内存消耗: 448K, 提交时间: 2023-07-09 19:50:18

#include<bits/stdc++.h>
using namespace std;
int n,a[302],b[302];
map<int,int> f;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    f[0]=0;
    for(int i=1;i<=n;++i){
        for(auto &[k,v]:f){
            int x=__gcd(k,a[i]);
            if(f[x]) f[x]=min(f[x],f[k]+b[i]);
            else f[x]=f[k]+b[i];
        }
    }
    cout<<(f[1]?f[1]:-1);
}