题意：n张卡，可跳跃的长度l[i],以及花费c[i]
起始点为0，问如果选卡使得可以每个点都能跳到，最小的花费是多少。
思路：本质就是选取一些卡，选择卡长度的gcd为1，，且花费最小。那么我们用map映射gcd值以及其对应的最小花费。最后输出mp[1]即可。(ps:可能有卡片长度相同)详见代码：
/********************************************************* file name: codeforces510D.cpp author : kereo create time: 2015年02月03日 星期二 16时25分06秒*********************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<set>#include<map>#include<vector>#include<stack>#include<cmath>#include<string>#include<algorithm>using namespace std;typedef long long ll;const int sigma_size=26;const int N=100+50;const int MAXN=300+50;const int inf=0x3fffffff;const double eps=1e-8;const int mod=100000000+7;#define L(x) (x<<1)#define R(x) (x<<1|1)#define PII pair<int, int>#define mk(x,y) make_pair((x),(y))int n;int a[MAXN],c[MAXN];map<int,int>mp; //记录gcd值为x对应的最小的代价vector<int>vec;int gcd(int a,int b){return b == 0 ? a : gcd(b,a%b);}int main(){while(~scanf("%d",&n)){mp.clear(); vec.clear();for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&c[i]);int res=a[1];for(int i=2;i<=n;i++)res=gcd(res,a[i]);if(res!=1){printf("-1\n");continue;}for(int i=1;i<=n;i++){if(mp[a[i]] == 0){mp[a[i]]=c[i];vec.push_back(a[i]);}else if(mp[a[i]]>c[i])mp[a[i]]=c[i];}for(int i=1;i<=n;i++){for(int j=0;j<vec.size();j++){int tmp=gcd(a[i],vec[j]);if(mp[tmp] == 0){vec.push_back(tmp);mp[tmp]=mp[vec[j]]+mp[a[i]];}else if(mp[tmp]>mp[vec[j]]+mp[a[i]])mp[tmp]=mp[vec[j]]+mp[a[i]];}}printf("%d\n",mp[1]);}return 0;}
爱上一个人的时候，总会有点害怕，怕得到他;怕失掉他。
