序号5:

想了很久的DP ,应该很简单，但是。。

题目直接转化为求n个数中选一些数GCD=1且花费最小

数比较大

map  HASH

还有一点 我们知道 GCD(X,X*Y)==X;

所以我的代码里不用考虑这点了

pasting

#include<stdio.h>

#include<algorithm>

#include<string>

#include<iostream>

#include<queue>

#include<cmath>

#include<string.h>

#include <vector>

#include<map>

using namespace std;

typedef long long ll;

map<int,int>mp;

int a[333],b[333];

#define inf 0x3f3f3f3f

map<int,int>::iterator it;

int gcd(int x,int y)

{

    if (x%y==0) return y;

    return gcd(y,x%y);

}

void dfs(int x,int y)

{

    if (!mp[x]) mp[x]=inf;

    mp[x]=min(mp[x],y);

    for (it=mp.begin();it!=mp.end();it++)

    {

        int tmp=(*it).first;

        int v=  (*it).second;

        int nw=gcd(tmp,x);

        if (!mp[nw]) mp[nw]=inf;

        mp[nw]=min(mp[nw],v+y);

    }

}

int main()

{

    int n;

    cin>>n;

    for (int i=1;i<=n;i++) cin>>a[i];

    for (int i=1;i<=n;i++) cin>>b[i];

        for (int i=1;i<=n;i++)

        dfs(a[i],b[i]);

        if (mp[1]==0) mp[1]=-1;

        cout<<mp[1];

    return 0;

}