Codeforces 512B Fox And Jumping dp+gcd

题目链接：点击打开链接

题意：

给定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");
    else
        printf("%d\n",mp[pre][1]);
}

Codeforces 512B Fox And Jumping dp+gcd

原文：http://blog.csdn.net/qq574857122/article/details/43453179