题目链接：点击打开链接
题意：
给定n个数
下面2行是n个数字和购买该数字的花费。
使得购买的数字能通过加减获得任意一个正整数。问最小的花费是多少。（购买得到的数字可以多次使用）
思路：
首先是要获得任意的正整数，其实就是获得1就可以了。
而获得1的话 只需要我们选的数的gcd = 1即可。
设 有整数x，y，要使得x y能构造任意一个整数，，充要条件就是gcd(x, y)=1
推论:
设int G = gcd(x, y);
则 ax+by = G( ax/G+by/G )
括号中能构成任意一个整数, 当G=1时才能使得ax+by 能组成1。
然后就是动态维护集合中每个gcd对应的最小花费。
#include <cstdio>#include <cstring>#include <string.h>#include <iostream>#include <algorithm>#include <queue>#include <vector>#include <cmath>#include <set>#include <map>using namespace std;int l[306];int c[306];int gcd(int a,int b){return b==0?a:gcd(b,a%b);}map<int,int>mp[2];map<int,int>::iterator it;int pre,cur;int hehe; int papa;void setMin(int x,int y){if(mp[cur].count(x)){if(y<mp[cur][x])mp[cur][x]=y;}else mp[cur][x]=y;}int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&l[i]);for(int i=1;i<=n;i++)scanf("%d",&c[i]);pre=0;cur=1;mp[0][l[1]]=c[1];for(int i=2;i<=n;i++){mp[cur].clear();mp[cur][l[i]]=c[i];for(it=mp[pre].begin();it!=mp[pre].end();it++){int x=it->first;int y=it->second;setMin(x,y);setMin(gcd(x,l[i]),y+c[i]);}swap(pre,cur);}if(!mp[pre].count(1))puts("-1");elseprintf("%d\n",mp[pre][1]);}
走走停停，不要害怕错过什么，
