序号: 

      想了很久的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 0x3f3f3f3fmap<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;}

寒假222_codeforces 290 div 2 D